目录
一、（leetcode 39）组合总和
基本的回溯方法遵循回溯模板，需要注意的是回溯中的startIndex是从当前i继续而不是i+1，因为组合中的数字允许重复。剪枝优化的思路是通过target这个限制条件。在基本回溯的过程中，终止条件是当前层的sum大于target，但如果之后的数比当前数大，那么后续的递归是多余的。因此可以同通过先排序，再防止进入大于target下一层的操作来进行剪枝优化。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex){
if(sum == target){
res.emplace_back(path);
return;
}
int len =candidates.size();
for(int i = startIndex; i < len && sum + candidates[i] <= target; ++i){
sum += candidates[i];
path.emplace_back(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
res.clear();
path.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return res;
}
};二、（leetcode 40）组合总和II
这题乍一看和上一题一样，无非就是同一个元素不能重复使用，似乎只要将层中的递归startIndex修改为i+1即可。但是这道题还有另一个难点，那就是数组中会出现重复的元素，同一位置的元素不能重复使用，同时最终答案也不能出现重复path，这就是一个判断树层去重（而不是树枝去重）的过程，为此加入一个used数组作为辅助判断。时间复杂度，空间复杂度。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used){
if(sum == target){
res.emplace_back(path);
return;
}
int len = candidates.size();
for(int i = startIndex; i < len && sum + candidates[i] <= target; ++i){
if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false){
continue;
}
sum += candidates[i];
path.emplace_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i+1, used);
sum -= candidates[i];
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
res.clear();
path.clear();
sort(candidates.begin(), candidates.end());
vector<bool> used(candidates.size(), false);
backtracking(candidates, target, 0, 0, used);
return res;
}
};这道题也可以不用used数组，直接判断与前一个位置相同的元素的下标是否是本身，即
if(i > startIndex && candidates[i] == candidates[i-1]) continue;三、（leetcode 131）分割回文串
这道题的主要步骤可以拆分成两个部分，如何分割和如何判断。如何分割其实就是组合问题，我们需要对每个组合进行判断，很自然地想到了回溯方法来进行穷举；至于如何判断，想到的第一种方法就是双指针一左一右进行判断（还有利用栈的特性，不过不比双指针效率高）。可以优化的部分就是利用动态规划对回文串进行判断，一个回文串的去两端子串也一定是回文串。但是实际的代码编写，还需要练习。主要难点如下：
- 切割问题可以抽象为组合问题
- 如何模拟那些切割线
- 切割问题中递归如何终止
- 在递归循环中如何截取子串
- 如何判断回文
class Solution {
public:
vector<vector<string>> res;
vector<string> path;
vector<vector<bool>>isPalindrome; // dp数组
void backtracking(const string& s, int startIndex){
if(startIndex >= s.size()){
res.emplace_back(path);
return;
}
int len = s.size();
for(int i = startIndex; i < len; ++i){
if(isPalindrome[startIndex][i]){
string str = s.substr(startIndex, i-startIndex+1);
path.emplace_back(str);
}else{
continue;
}
backtracking(s, i+1);
path.pop_back();
}
}
void computePalindrome(const string& s){
int len = s.size();
isPalindrome.resize(len, vector<bool>(len, false));
for(int i = len-1; i >= 0; --i){
for(int j = i; j < len; ++j){
if(j == i){
isPalindrome[i][j] = true;
}else if(j - i == 1){
isPalindrome[i][j] = (s[i] == s[j]);
}else{
isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);
}
}
}
}
vector<vector<string>> partition(string s) {
res.clear();
path.clear();
computePalindrome(s);
backtracking(s, 0);
return res;
}
};