组合问题：
同一个集合，startindex
允许重复元素startindex从i开始
不允许重复元素，startindex从i+1开始
不同集合，index（可以用for，不用用回溯）
for循环，横向遍历，控制组合不重复；
递归，for内部，纵向便利，控制组合内元素如何构成。
剪枝从元素个数和元素和入手，元素和用排序+剪枝，都是在for的结束上做文章
39. 组合总和
如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合
在求和问题中，排序之后加剪枝是常见的套路！
class Solution {
public:
void backtracing(vector<vector<int>>& res, vector<int>& path, vector<int>& candidates, int target, int sum, int start_index){
if(target<sum){
return;
}
if(target==sum){
res.push_back(path);
return;
}
for(int i=start_index;i<candidates.size() && sum+candidates[i]<=target;i++){
path.push_back(candidates[i]);
sum += candidates[i];
backtracing(res, path, candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> path;
sort(candidates.begin(), candidates.end());
backtracing(result, path, candidates, target, 0, 0);
return result;
}
};40.组合总和II
组合不能重复：
同层/树层
for()怎么循环
元素不能重复：
backtracing(...,i+1,...)
for循环控制的是组合，for里面控制的是深度，元素怎么构建。
class Solution {
public:
void backtracing(vector<vector<int>>& res, vector<int>& path, vector<int>& candidates, int target, int sum, int start_index){
if(sum>target){
return;
}
if(sum==target){
res.push_back(path);
return;
}
for(int i=start_index;i<candidates.size()&&sum+candidates[i]<=target;i++){
if(i>start_index && candidates[i]==candidates[i-1]){
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
backtracing(res, path, candidates, target, sum, i+1);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> path;
sort(candidates.begin(),candidates.end());
backtracing(result, path, candidates, target, 0, 0);
return result;
}
};131.分割回文串
分割问题跟组合问题一样，都是重叠子问题+记录path。注意定义好分割的区间。
class Solution {
public:
void backtracking(vector<vector<string>>& res, vector<string>& path, string s, int start_index){
if(start_index>=s.size()){
res.push_back(path);
return;
}
for(int i=start_index;i<s.size();i++){
string mid = s.substr(start_index, i-start_index+1);
if(isHuiwenchuan(mid)){
path.push_back(mid);
backtracking(res, path, s, i+1);
path.pop_back();
}
}
}
bool isHuiwenchuan(string s){
for(int i=0,j=s.size()-1;i<j;i++,j--){
if(s[i] != s[j]){
return false;
}
}
return true;
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
backtracking(result, path, s, 0);
return result;
}
};