93.复原IP地址 

切割字符串，并且在每一个切割过的字符串后面加上 ‘ .’

返回条件：逗点个数==3

        如果最后一小节符合要求，就将该字符串添加到结果集中

循环中：从start到i 符合要求，就继续添加逗点和字符

        不符合下面就不用看了。

不要试图一下找完，从第一个开始算。

class Solution {
private:
vector <string> result;void transfer(string&s,int start,int pointnum){if(pointnum==3){if(isVaild(s,start,s.size()-1)){result.push_back(s);}return;}for(int i=start;i<s.size();i++){if(isVaild(s,start,i)){s.insert(s.begin() + i + 1,'.');pointnum++;transfer(s,i+2,pointnum);pointnum--;s.erase(s.begin()+i+1);}else{break;}}}bool isVaild(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0开头的数字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法return false;}num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;}public:vector<string> restoreIpAddresses(string s) {result.clear();if(s.size()<4||s.size()>12) return result;transfer(s,0,0);return result;}
};

78.子集 

结束条件+回溯过程

class Solution {
private:
vector<vector<int>> result;
vector<int> partset;void transfer(vector<int>& nums,int start){result.push_back(partset);if(start>=nums.size()){return;}for(int i=start;i<nums.size();i++){partset.push_back(nums[i]);transfer(nums,i+1);partset.pop_back();}
}public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();partset.clear();transfer(nums,0);return result;}
};

90.子集II  

只是判断生成的子集是否重复

子集重复就是数字重复，和上一级递归的数字比较是否使用过

class Solution {
private:
vector<vector<int>> result;
vector<int> partset;void transfer(vector<int>& nums,int start,vector<bool> used){result.push_back(partset);for(int i=start;i<nums.size();i++){//数字重复             上一个已经使用过if(i>start&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}used[i]==true;partset.push_back(nums[i]);transfer(nums,i+1,used);used[i]=false;partset.pop_back();}
}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {result.clear();partset.clear();sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);transfer(nums,0,used);return result;}
};