39. 组合总和
思路：
这道题的思路与之前题目思路相似，只不过candidate里面的数可以重复使用，所以在进行递归操作的时候传入的参数需要留意。
代码：
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& candidates, int target,int sum,int index)
{
if(sum>target)return;
if(sum==target)
{
res.push_back(path);
return;
}
for(int i=index;i<candidates.size();i++)
{
path.push_back(candidates[i]);
sum+=candidates[i];
backtracking(candidates,target,sum,i);
sum-=candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates,target,0,0);
return res;
}
};
40. 组合总和 II
思路：
这道题的难点在于原本的candidate数组中含有重复的元素，但是输出的结果在组合逻辑上不能重复，这就要求做去重处理，在对原来数组经过排序后，相同的元素在相邻的位置，在元素遍历的过程中就只需要使用第一个元素，后面的元素直接跳过即可，这样的逻辑可以用一个与原数组相同大小的标志数组used表示，如果相同的几个元素中最开始的元素uesd标志位为1，则表示首位已经搜索，后面的无需再搜索，直接跳过即可。
代码：
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& candidates, int target,int sum,int index,vector<bool> used)
{
if(sum>target) return;
if(sum==target)
{
res.push_back(path);
return;
}
for(int i=index;i<candidates.size();i++)
{
if(i>0 && used[i-1]==false && candidates[i]==candidates[i-1]) continue;
path.push_back(candidates[i]);
used[i]=true;
sum+=candidates[i];
backtracking(candidates,target,sum,i+1,used);
sum-=candidates[i];
used[i]=false;
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(),false);
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0,used);
return res;
}
};
131. 分割回文串
代码：
class Solution {
public:
vector<string> path;
vector<vector<string>> res;
void backtracking(const string& s,int index)
{
if(index>=s.size())
{
res.push_back(path);
return;
}
for (int i = index; i < s.size(); i++) {
if (isPalindrome(s, index, i)) {
string str = s.substr(index, i - index + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
}
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<vector<string>> partition(string s) {
backtracking(s, 0);
return res;
}
};
