第一題：

原題鏈接：78. 子集 - 力扣（LeetCode）

思路：

本題很簡單，就是在每次遍歷的地方都要搜集結果。

終止條件：當前要收集的起始位置已經大于等于數組的大小的時候證明已經搜集到完成了。

代碼如下：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return res;}
private:vector<vector<int>> res;vector<int> path;void backtracking(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]);backtracking(nums, i + 1);path.pop_back();}}
};

第二題：

原題鏈接：90. 子集 II - 力扣（LeetCode）

思路：

本題和子集很相似，但是要注意的是本題有重復的元素，但是結果中不能包含重復的子集。

和之前的一道題很相似40. 組合總和 II - 力扣（LeetCode），都是樹層和樹枝去重的邏輯。

用一個bool類型的數據來記錄當前元素是否被遍歷過。

carl說也可以不用使用bool類型的數組記錄，因為遞歸的時候下一個startIndex是i+1而不是0。如果要是全排列的話，每次要從0開始遍歷，為了跳過已入棧的元素，需要使用used。

這題一開始要進行排序才行。

代碼如下：

class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return res;}
private:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int startIndex, vector<bool> used){res.push_back(path);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();}}
};

第三題：

原題鏈接：93. 復原 IP 地址 - 力扣（LeetCode）

思路：

終止條件：

用一個count值來記錄當前遍歷到IP地址的第幾個字段了，如果當前已經遍歷到第三個字段的時候，就需要考慮剩下的字符是否符合要求，如果符合要求的話就將剩下的結果添加到path中，如何將path添加到res結果數組中。接下來是重點，這里需要回溯，我因為沒有回溯出現了很大的問題。

在for循環中就是判斷當前截取的字符串是否符合要求，如果符合要求的話就將該字符串添加到path路徑中同時添加一個“.”，然后count++；接著就是遞歸加回溯。

回溯的話要注意pop掉你添加進去的，不能只pop一次。

在判斷是否符合IP字段要求的函數中需要注意，有一個@字符需要判斷。然后用sum來記錄所有當前字段的int值并進行判斷。我使用stoi函數失敗了。

代碼如下：

class Solution {
public:vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return res;}
private:vector<string> res;string path;void backtracking(string s, int startIndex, int count){if(count == 3){if(isIP(s, startIndex, s.size() - 1)){path += s.substr(startIndex, s.size() - 1 - startIndex + 1);res.push_back(path);// 回溯for(int i = 0; i < s.size() - startIndex; i++) {path.pop_back();}return;return;}}for(int i = startIndex; i < s.size(); i++){if(isIP(s, startIndex, i)){string st = s.substr(startIndex, i - startIndex + 1);int size = st.size();path += st;path += ".";count += 1;backtracking(s, i + 1, count);count -= 1;path.pop_back();while(size){path.pop_back();size--;}}}}bool isIP(const string& s, int start, int end){if(start > end) return false;if(start != end && s[start] == '0') return false;int sum = 0;for(int i = start; i <= end; i++){if(s[i] == '@')return false;else{sum = sum * 10 + (s[i] - '0');}if(sum > 255){return false;}}return true;}
};