1.leetcode 39.组合总和
这道题里面的数组里面的数字是可以重复使用的，那可能就会有人想，出现了0怎么办，有这个想法的很好，但是题目要求数组里面的数字最小值为1，这就可以让人放心了。但是有总和的限制，所以间接的也有个数的限制。
因为没有个数的限制，所以可能递归没有层数的限制，但是只要选取的元素总和超过了target，就返回。
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
if(sum>target){
return;
}
if(sum==target){
result.push_back(path);
return;
}
for(int i=startIndex;i<candidates.size();i++){
sum+=candidates[i];
path.push_back(candidates[i]);
backtracking(candidates,target,sum,i);// 不用i+1了，表示可以重复读取当前的数
sum-=candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates,target,0,0);
return result;
}
};思路总结：这道题有两点不同：组合没有数量要求以及元素可以无限重复选取。
2.leetcode 40.组合总和II
这道题和上一道题目的区别：第一，本题的数组中的每个数字在每个组合中只能使用一次，第二，本题数组的元素是有重复的，而上一题是无重复元素的数组。
最后本题和上一道题的要求是一样的，解集不能包含重复的组合。
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！
所以要在搜索的过程中就去掉重复组合。
很多同学在去重的问题上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。
这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){
if(sum==target){
result.push_back(path);
return;
}
for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
continue;
}
sum+=candidates[i];
path.push_back(candidates[i]);
used[i]=true;
backtracking(candidates,target,sum,i+1,used);// 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
used[i]=false;
sum-=candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(),false);
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0,used);
return result;
}
};补充：这里直接使用startIndex来去重也是可以的，就可以不用used数组。
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
if(sum==target){
result.push_back(path);
return;
}
for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
// 要对同一树层使用过的元素进行跳过
if(i>startIndex&&candidates[i]==candidates[i-1]){
continue;
}
sum+=candidates[i];
path.push_back(candidates[i]);
backtracking(candidates,target,sum,i+1);// 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
sum-=candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0);
return result;
}
};思路总结：关键是去重的逻辑，代码很简单，网上一搜一大把，但几乎没有能把这块代码含义讲明白的，基本都是给出代码，然后说这就是去重了，究竟怎么个去重法也是模棱两可。
3.leetcode 131.分割回文串
回文串就是向前和向后读都是相同的字符串。
本题涉及到两个关键问题：第一，切割问题，有不同的切割方式，第二，判断回文。
我们来分析一下切割，其实切割问题类似组合问题。
例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段。
class Solution {
public:
vector<vector<string>> result;
vector<string> path;// 放已经回文的子串
//判断是否为回文串
bool isH(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;
}
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++){
if(isH(s,startIndex,i)){// 是回文子串
// 获取[startIndex,i]在s中的子串
string str=s.substr(startIndex,i-startIndex+1);
path.push_back(str);
}
else{// 不是回文，跳过
continue;
}
backtracking(s,i+1);// 寻找i+1为起始位置的子串
path.pop_back();// 回溯过程，弹出本次已经添加的子串
}
}
vector<vector<string>> partition(string s) {
backtracking(s,0);
return result;
}
};思路总结：
这道题目在leetcode上是中等，但可以说是hard的题目了，但是代码其实就是按照模板的样子来的。
那么难究竟难在什么地方呢？
我列出如下几个难点：
- 切割问题可以抽象为组合问题
- 如何模拟那些切割线
- 切割问题中递归如何终止
- 在递归循环中如何截取子串
- 如何判断回文
我们平时在做难题的时候，总结出来难究竟难在哪里也是一种需要锻炼的能力。
一些同学可能遇到题目比较难，但是不知道题目难在哪里，反正就是很难。其实这样还是思维不够清晰，这种总结的能力需要多接触多锻炼。
本题我相信很多同学主要卡在了第一个难点上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。
如果意识到这一点，算是重大突破了。接下来就可以对着模板照葫芦画瓢。
但接下来如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。
关于模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线
除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。
所以本题应该是一道hard题目了。