一、分割回文串
1.题目
131. 分割回文串 - 力扣（LeetCode）
2.思路
分割回文串可以抽象为一棵树形结构。
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
2.1 传入参数
result存储结果
path进行收集
startIndex标记当前切割线位置
2.2 终止条件
那么在代码里什么是切割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
2.3 单层循环逻辑
在递归循环中如何截取子串呢？
在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串。
判断回文串函数：
使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。
总体代码：
class Solution {
private:vector<vector<string>> result;vector<string> path;void backtracking(const string& s,int startIndex){// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了if(startIndex == s.size()){result.push_back(path);return;}//单层循环逻辑for(int i = startIndex;i < s.size();i++){//path收集if(ispalidrome(s,startIndex,i)){string str = s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{//没有则跳出该次收集continue;}backtracking(s,i+1);path.pop_back();}}bool ispalidrome(const string& s,int start,int end){for(int i = start,j = end;i < j;i++,j--){if(s[i] != s[j]){return false;}}return true;}public:vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s,0);return result;}
};二、复原IP地址
1.题目
93. 复原 IP 地址 - 力扣（LeetCode）
2.思路
其实只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的131.分割回文串 (opens new window)就十分类似了。
切割问题可以抽象为树型结构，如图：
2.1 传入参数
startIndex是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum，记录添加逗点的数量。（可以记录切割到哪一部分）
2.2 终止条件
本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
然后验证一下第四段是否合法，如果合法就加入到结果集里。
2.3 单层循环逻辑
和分割回文串一样，在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.表示已经分割。如果不合法就结束本层循环，如图中剪掉的分支。
然后就是递归和回溯的过程：（）
递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。（insert函数和erase函数）
判断子串是否合法
主要考虑到如下三点：
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
总体代码：
class Solution {
private:vector<string> result;void backtracking(string& s,int startIndex,int pointNum){if(pointNum == 3){// 判断第四段子字符串是否合法，如果合法就放进result中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)){//比较是否为0~255的数s.insert(s.begin()+i+1,'.');pointNum++;backtracking(s,i+2,pointNum);pointNum--;s.erase(s.begin()+i+1);}else break;}}bool isValid(const string& s,int start,int end){if(start > end) return false;//同时要保证不是单个0if(s[start] == '0' && start != end) 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){return false;}}return true;}
public:vector<string> restoreIpAddresses(string s) {result.clear();if(s.size() < 4 || s.size() > 12) return result;backtracking(s,0,0);return result;}
};
三、子集
1.题目
78. 子集 - 力扣（LeetCode）
2.思路
如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
什么时候for可以从0开始呢？
求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。
以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
2.1 传入参数
2.2 终止条件
2.3 单层循环逻辑
把每次遍历的数字加进去path。
总体代码：
class Solution {
private:vector<vector<int>> result;vector<int> path;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();}}public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return result;}
};
