93.復原IP地址

思路：要建立一個判斷子字符串是否合法的函數，判斷多種不合法的情況。在回溯函數中，參數除了s,和startindex還需要一個pointNum來記錄句點的數量，當句點的數量等于3時，判斷最后一個子串是否合法，如果合法就將s輸入到result中，本題都是在字符串s的基礎上加句點，沒有生成新的字符串。如果s的長度小于4或者大于12，直接return result，剪枝。

class Solution {
public:
vector<string> result;bool isValid(string &s,int start,int end){if(start>end){return false;}if(s[start]=='0'&&start!=end)//s不等于字符的'0'{return false;}int num=0;for(int i =start;i<=end;i++){num= num*10+s[i]-'0';if(num>255){return false;}}return true;}void backtracking(string &s,int startindex,int pointNum){//終止條件,句點數為3，且最后一段合法if(pointNum==3){if(isValid(s,startindex,s.size()-1)){result.push_back(s);}return;}for(int i =startindex;i<s.size();i++){if(isValid(s,startindex,i)){s.insert(s.begin()+i+1,'.');pointNum++;backtracking(s,i+2,pointNum);s.erase(s.begin()+i+1);pointNum--;}else{break;}}}vector<string> restoreIpAddresses(string s) {result.clear();if(s.size()<4||s.size()>12){return result;}backtracking(s,0,0);return result;}
};

78.子集

思路：與組合問題、分割問題類似，從整數數組中找到互不相同的不重復子集。

在回溯函數中，先result.push_back(path)，先將子集的元素輸入進result，終止條件就是當startindex==nums.size()時返回，在單層邏輯中找尋滿足條件的不重復子集。

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

90.子集II

思路：子集II相比于上一題，整數數組中包含重復元素，但子集不能包含重復子集。這個題跟之前做過的一道題思路相像，需要先對nums排序，然后利用used判斷繼續生成的子集是否為重復子集，如果是重復的直接continue。

class Solution {
public:
vector<int> path;
vector<vector<int>> result;void backtracking(vector<int>&nums,int startindex,vector<bool> used){result.push_back(path);if(startindex==nums.size()){return;}for(int i =startindex;i<nums.size();i++){if(i>0 && nums[i]==nums[i-1] && used[i-1] == false){continue;}path.push_back(nums[i]);used[i] = true;backtracking(nums,i+1,used);used[i] = false;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {path.clear();result.clear();vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return result;}
};

收獲：

處理子集問題與組合和分割問題不同點在于，在回溯函數內先result.push_back(path),先把子集加入結果集。因為需要在每一個節點都收獲結果，而組合和分割問題只需要在葉子節點收獲結果。