分割问题类似于组合问题，在分割一个元素后，在剩下元素中继续分割，那么分割问题也可以抽象为一颗树形结构：
class Solution {
public:
vector> result;
vector path;
void backtracking(const string& s, int start) { //start为递归遍历的起始位置
if (start >= s.size()) { //遍历到了字符串的最后
result.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) { //如果是回文串
string str = s.substr(start, i - start + 1); //获取[start,i]在s中的子串
path.push_back(str);
}
else continue; //如果不是回文串则直接跳过
backtracking(s, i + 1); //寻找i+1为起始位置的子串，不能重复切割所以为i+1
path.pop_back(); //回溯，弹出本次填在path里的子串
}
}
bool isPalindrome(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;
}
vector> partition(string s) {
backtracking(s, 0);
return result;
}
};
代码理解起来并不难，但真正写的时候要注意的太多了，在题解中还有很多用到动态规划的，后续有时间再返回看看
题目2：93.复原IP地址
同样抽象为N叉树结构，其实解题的思路和131差不多
class Solution {
public:
vector result;
void backtracking(string& s, int start, int pointnum) { //start:搜索的起始位置，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)) { //判断子串[start,i]合法并截取
s.insert(s.begin() + i + 1, '.'); //如果合法就在子串后加'.'
pointnum++;
backtracking(s, i + 2, pointnum); //插入逗点后下一个子串位置为i+2
pointnum--; //回溯并删除逗点
s.erase(s.begin() + i + 1);
}
else break; //如果子串不合法则直接结束本层循环
}
}
bool isvaild(const string& s, int start, int end) { //判断子串[start,end]是否合法
if (start > end) return false;
if (s[start] == '0' && start != end) return false; //0开否的数字不合法
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; //大于255不合法
}
return true;
}
vector restoreIpAddresses(string s) {
backtracking(s, 0, 0);
return result;
}
};
题目3：78.子集
子集问题可以理解为找N叉树的所有节点。
代码虽然看起来简单，但是非常的巧妙，注意打上断点推一遍
class Solution {
public:
vector> result;
vector path;
void backtracking(vector& nums, int start) {
result.push_back(path); //要放在终止添加的上面，不然会漏掉集合本身
if (start >= nums.size()) return; //这里终止条件可以不加，因为start >= nums.size()会跳出for循环
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]); //子集收集元素
backtracking(nums, i + 1); //从i+1开始，元素不重复取
path.pop_back(); //回溯
}
}
vector> subsets(vector& nums) {
backtracking(nums, 0);
return result;
}
};
题目4：90.子集Ⅱ
这一题和78题相比，集合里有重复的元素，因此需要对求取的子集进行去重。
去重的方法和之前40.组合总和Ⅱ是一样的
那么就相当于78题求子集加上去重
class Solution {
public:
vector> result;
vector path;
void backtracking(vector& nums, int start) {
result.push_back(path);
for (int i = start; i < nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector> subsetsWithDup(vector& nums) {
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return result;
}
};
也可以使用哈希表进行去重：
class Solution {
public:
vector> result;
vector path;
void backtracking(vector& nums, int startIndex) {
result.push_back(path);
unordered_set used;
for (int i = startIndex; i < nums.size(); i++) {
if (used.find(nums[i]) != used.end()) {
continue;
}
used.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector> subsetsWithDup(vector& nums) {
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0);
return result;
}
};
题目5：491.递增子序列
class Solution {
public:
vector> result;
vector path;
void backtracking(vector& nums, int start) {
if (path.size() > 1) result.push_back(path); //不加return，因为要取树上所有符合条件的节点
unordered_set used; //通过set对本层元素进行去重
for (int i = start; i < nums.size(); i++) { //(子序列不能为空 且 所取元素大于子序列最后一个元素) 或 (同一树层没有重复选取元素)
if ((!path.empty() && nums[i] < path.back()) || used.find(nums[i]) != used.end()) continue;
used.insert(nums[i]); //记录元素、防止本层后面再取
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector> findSubsequences(vector& nums) {
backtracking(nums, 0);
return result;
}
};
