一、前言：
参考文献：代码随想录
今天的主题内容是回溯算法，这一章的干货很多，我需要慢慢的品味，不单单只是表象，还需要研究深层原理。
二、复原IP地址
1、思路：
（1）首先还是确定返回值和参数：
void backtracking(string &s, int startIndex, int pointSum)这里比往常多了一个pointSum，这个是来判断是否符合ip格式的一个标志，也就是记录这个s中存在多少个"."；
（2）终止条件如下：
// pointsum是用来判断这个字符串中存在多少个"."如果有了三个，就说明满足IP格式了if (pointSum == 3) {if (isValud(s, startIndex, s.size() - 1)) {// 这里还有一个条件就是判断最后的一段是否符合IP要求result.push_back(s);}return;} 这里首先要判断是否有三个”.“，存在之后，再判断最后的那一段是否符合IP的格式，然后才能插入，如果不符合那就直接return回溯了。
（3）单层递归逻辑：
for (int i = startIndex; i < s.size(); i++) {if (isValud(s, startIndex, i)) {s.insert(s.begin() + i + 1, '.'); // 插入"."pointSum++;backtracking(s, i + 2, pointSum); // 这里是 i+2 此逻辑是因为加了"."需要多加一个1// 回溯pointSum--;s.erase(s.begin() + i + 1); // 删除"."} else {break;}}看起来并不复杂，但是，难疑点比较多。首先就是先判断当前的这个切片处是否符合IP格式，然后再进行插入逗点，pointSum再做记录，然后就可以开始递归了，这里的是 i+2的，因为这个时候插入了逗点，所以需要后移一位，接着就是回溯了。
（4）主函数中存在一个小小的剪枝操作，如下：
if (s.size() < 4 || s.size() > 12) return result;（5）判断是否为ip的函数为：
bool isValud(string &s, int start, int end) {if (start > end) {return false;}// 头号字符不能为0（只有一位时可以）if (s[start] == '0' && start != end) {return false;}// 小于等于255int 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) {return false;}}return true;}这里的细节也比多：
1、start和end的比较；
2、头数字不为0，且不是只有一个数字；
3、和小于等于255；
2、整体代码如下：
class Solution {
private:// 判断是否为合法IPbool isValud(string &s, int start, int end) {if (start > end) {return false;}// 头号字符不能为0（只有一位时可以）if (s[start] == '0' && start != end) {return false;}// 小于等于255int 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) {return false;}}return true;}vector<string> result;void backtracking(string &s, int startIndex, int pointSum) { // pointsum是用来判断这个字符串中存在多少个"."如果有了三个，就说明满足IP格式了if (pointSum == 3) {if (isValud(s, startIndex, s.size() - 1)) {// 这里还有一个条件就是判断最后的一段是否符合IP要求result.push_back(s);}return;} // 单层递归逻辑for (int i = startIndex; i < s.size(); i++) {if (isValud(s, startIndex, i)) {s.insert(s.begin() + i + 1, '.'); // 插入"."pointSum++;backtracking(s, i + 2, pointSum); // 这里是 i+2 此逻辑是因为加了"."需要多加一个1// 回溯pointSum--;s.erase(s.begin() + i + 1); // 删除"."} else {break;}}}
public:vector<string> restoreIpAddresses(string s) {if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了backtracking(s, 0 , 0);return result;}
};三、子集
1、思路：
（1）返回值和终止条件并没有什么改变：
void backtracking(vector<int> &nums, startIndex)(2)终止条件（这个条件可有可不有，因为在return时以及到了叶子节点处，循环自然就不去了，就不用手动终止了）：
if (startIndex >= nums.size()) return;（3）单层递归逻辑：
for (int i = startIndex; i < nums.size(); i++) {// 插入元素path.push_back(nums[i]);// 递归backtracking(nums, i + 1);// 回溯path.pop_back();}还是插入，递归，回溯。。。
（4）最重要的就是收集path，在每次递归开始时就可以收集子集了；
2、整体代码如下：
class Solution {
private: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();}return;}
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};四、子集||
1、思路：
这个题目和上一题加上组合总和|||综合，这里也需要添加一个used来判断是否使用了这个元素，如果使用了那就可以继续遍历，说明在树枝上，但是如前面一个元素相同，但是没有被使用，说明在数层上面，就需要跳过这个数字了，避免重复。
图解如下：
这里就不一步步分析了；
2、整体代码如下：
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startIndex, vector<bool> &used) {result.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();}return;}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return result;}
};今日学习时间：2小时
leave message:
Her behavior is well-accorded with the expectations of her parents.
她的行为与父母的期望相符。
