复原IP地址
题目理解
1.给出的是字符串，IP地址在【0，255】之间，字符串转数字；
2.0可以单独出现，但是不能跟数字出现；
3.字符串中要插入'.';
4.字符串的大小范围在4~12之间；
5.不能有除数字外的字母；
思路
首先确定答案类型：vector<string> res，一个用来存单个有效IP地址的字符串str；
1.函数返回值：void，函数参数，传进来的string s;
2.确定终止条件：插入4个'.'后；
3.单层回溯：
for循环遍历树的宽度:每次startIndex后移一位；
树的深度：每次.后移一位。后移两位。
问题
1.怎么在字符串中插入.? s.insert(pos,'neirong')
if(start>end){return false;}该条件是在处理空的字符串！很难想到这个边界条件。
class Solution {
public:vector<string> res;void backtrack(string& s, int startIndex, int pointNum) {if (pointNum == 3) {if (isValid(s, startIndex, s.size() - 1)) {res.push_back(s);}return;}for (int i = startIndex; i < s.size(); i++) {if (isValid(s, startIndex, i)) {s.insert(s.begin() + i + 1, '.');pointNum++;backtrack(s, i + 2, pointNum);s.erase(s.begin() + i + 1);pointNum--;} else {break;}}return;}bool isValid(const string& s, int start, int end) {if (start > end) {return false;} // 输入：s=101023 输出：10.102.3.if (s[start] == '0' && start != end) {return false;}int sum = 0;for (int i = start; i <= end; i++) {if (s[i] < '0' || s[i] > '9') {return false;}// 255逻辑sum = sum * 10 + (s[i] - '0');if (sum > 255) {return false;}}return true;}vector<string> restoreIpAddresses(string s) {backtrack(s, 0, 0);return res;}
};
求整数数组的所有子集
开始的时候在想每个整数数组都包含一个空的子集如何处理？写出来了但是不知道在哪里处理到了？
class Solution {
public:vector<int>path;vector<vector<int>> res;void backtrack(vector<int>&nums, int startIndex){res.push_back(path);if(startIndex>=nums.size()){return;}for(int i=startIndex;i<nums.size();i++){path.push_back(nums[i]);backtrack(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {res.clear();path.clear();backtrack(nums,0);return res;}
};
求存在重复元素的整数数组的子集
事情开始变得诡异起来了
让我再梳理一下事情的发生过程：
复用不存在重复元素的整数数组子集的代码；
其次，结果用set存下来，使用类型转换；
给path排序，发生了：
换给nums排序程序奇怪地运行起来了。
不懂。
class Solution {
public:vector<int>path;set<vector<int>> res;void backtrack(vector<int>&nums, int startIndex){res.insert(path);if(startIndex>=nums.size()){return;}for(int i=startIndex;i<nums.size();i++){path.push_back(nums[i]);backtrack(nums,i+1);path.pop_back();//} }vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());backtrack(nums,0);return vector<vector<int>>(res.begin(),res.end());}
};