题目：39. 组合总和、40.组合总和II、131.分割回文串
参考链接：代码随想录
39. 组合总和
思路：本题有点像以前做过的k数之和，前者使用的是双指针法，但本题没给定取的数的个数，故只能用回溯法。本题同一个数字可以重复取，但我们还是要设置开始位置，我们采用target递减的方法来判断总和。返回条件为target==0，for循环遍历第一个元素的选择，递归遍历后续元素的选择。当目前后续元素大于所需和的时候直接返回（剪枝），注意首先要对数组排序。时间复杂度O(n*2^n)。
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int begin){
if(target==0){
ans.push_back(path);
return;
}
for(int i=begin;i<=candidates.size()-1;i++){
if(target<candidates[i]){//剩下的所需和小于目前候选的元素，直接返回
return;
}
path.push_back(candidates[i]);
backtracking(candidates,target-candidates[i],i);//下一层递归依旧从i开始，因为可以重复
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0);
return ans;
}
};
标答还是使用的sum求和的方法，我们的方法更简单。
40.组合总和II
思路：本题和上题的区别是不能一个元素重复选择，所以只要把递归调用的参数的i改为i+1即可。但仅仅做这一个改动会导致结果重复的情况，一开始的错误代码：
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int begin){
if(target==0){
ans.push_back(path);
return;
}
for(int i=begin;i<=candidates.size()-1;i++){
if(target<candidates[i]){//剪枝
return;
}
path.push_back(candidates[i]);
backtracking(candidates,target-candidates[i],i+1);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0);
return ans;
}
};
一个比较容易的修改方法是直接对结果ans使用set去重处理，即先将vector转换为set，然后转回来即完成了去重操作。
set<vector<int>> s(ans.begin(),ans.end());
ans.assign(s.begin(),s.end());
但是在力扣中提交会出现超出内存限制，说明这种方法不够简洁，需要思考在生成ans的过程中就直接完成去重的方法。比如示例中排序后为[1,1,2,5,6,7,10]，当遇到连续几个相同的数时，我想到的方法是此时begin无论从哪里开始，第一次都要把这几个数都选进去，比如第一次for循环，begin=1，这里第二个1也要选入path，然后从第三个数（第一个不是1的数）开始递归；当第二次for循环，begin=2的时候，即可正常运行，这样就可以完成去重。再举一个例子，[1,1,1,1,1,2,3,4]，第一次for选入5个1，第二次选入4个，依此类推即可，则考虑到了path中1的个数的每一种情况。但是这种思路我的代码实在写不出来。
看看标答的去重思路，使用了一个used数组。去重主要是在同一树层上不能选择重复的值，bool型数组used用于记录元素是否被使用过。如图所示：
**当 can[i]==can[i-1] 时，即说明出现了重复的元素，此时要判断i-1位置的used值，如果为1，则说明已经被选取，是树枝上的元素，可以重复，如果为0，说明为数层上的元素，不能重复选取。**时间复杂度O(n*2^n)。
代码如下：
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int begin,vector<int> &used){
if(target==0){
ans.push_back(path);
return;
}
for(int i=begin;i<=candidates.size()-1;i++){
if(target<candidates[i]){//剪枝
return;
}
if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==0){
continue;//去重过程，树层相邻的相同则直接跳过
}
path.push_back(candidates[i]);
used[i]=1;
backtracking(candidates,target-candidates[i],i+1,used);
path.pop_back();
used[i]=0;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<int> used(candidates.size(),0);
backtracking(candidates,target,0,used);
return ans;
}
};
重点掌握去重逻辑。
看完标答发现直接使用begin去重也可以，跳过即目前的i与前一个相同时continue。
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int begin){
if(target==0){
ans.push_back(path);
return;
}
for(int i=begin;i<=candidates.size()-1;i++){
if(target<candidates[i]){//剪枝
return;
}
if(i>begin && candidates[i]==candidates[i-1]){
continue;//去重过程，树层相邻的相同则直接跳过
}
path.push_back(candidates[i]);
backtracking(candidates,target-candidates[i],i+1);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0);
return ans;
}
};
还是used数组方法好理解一些。
一个细节：在力扣中写c++代码的时候尽量少用数组，多用vector，力扣的C++有很多编译器没有的问题。
131.分割回文串
思路：首先是判断回文串，这个比较容易，用双指针法很快就可以写出一个判断函数。主要是切割，还是先确定两个参数，即切割开始begin和结束end，区间为[begin，end)，当完成一次切割后，下一次切割为[end，end+1)。故返回条件为切割完毕，此时下一个backtracking的end参数为size+1越界，这即为返回条件。for循环对于第一次切割的end位置循环，从1一直到size。一旦第一次切割的不是回文串，直接continue进入下一种切割。时间复杂度O(n*2^n)。
class Solution {
public:
bool isPalindrome(const string s,int begin,int end){//左闭右开，判断begin到end是不是回文串
while(begin<=end){
if(s[begin]!=s[end-1]){
return false;
}
begin++;
end--;
}
return true;
}
vector<vector<string>> ans;
vector<string> path;
void backtracking(const string s,int begin,int end){//begin为开始位置，end为切割位置
if(end>s.size()){//切割结束,
ans.push_back(path);
return;
}
for(int i=end;i<=s.size();i++){
if(!isPalindrome(s,begin,i)){//第一次切割就不是回文串，直接下一种切割
continue;
}
//第一种切割是回文串
path.push_back(string(s.begin()+begin,s.begin()+i));//加入结果
backtracking(s,i,i+1);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
backtracking(s,0,1);
return ans;
}
};
标答只传了一个参数start，但是多了一个求子串的操作，我们的方法更简单，空间占用更小。
标答的优化求回文串我没看太懂，二刷再细看，本题主要还是掌握回溯。