39. 组合总和
代码链接：https://leetcode.cn/problems/combination-sum/
算法思想：
采用回溯的思想，由于数字可以重复使用，因此startindex从上一个循环的i开始。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
int sum = 0;
void huisu(vector<int>& can, int target, int startindex)
{
if(sum==target)
{
res.push_back(path);
return;
}
if(sum>target)
return;
for(int i=startindex;i<can.size();i++)
{
sum = sum+can[i];
path.push_back(can[i]);
huisu(can,target,i);
path.pop_back();
sum = sum-can[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
huisu(candidates, target,0);
return res;
}
};
40. 组合总和 II
题目链接：https://leetcode.cn/problems/combination-sum-ii/
算法思想：
采用回溯。遇到需要去重的问题，需要把数组先排序，跳过重复元素进行处理。
代码：
class Solution {
public:
vector<vector<int>> final;
vector<int> path;
int sum = 0;
void huisu(vector<int>& candidates, int target, int start)
{
if(sum == target)
{
final.push_back(path);
return;
}
if(sum>target)
return;
for(int i=start;i<candidates.size();i++)
{
// cout<<"i="<<i<<endl;
if(i==start||candidates[i] != candidates[i-1])
{
// cout<<candidates[i-1]<<" "<<candidates[i]<<endl;
path.push_back(candidates[i]);
sum = sum + candidates[i];
huisu(candidates, target, i+1);
path.pop_back();
sum = sum-candidates[i];
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
huisu(candidates, target, 0);
return final;
}
};
131. 分割回文串
题目链接：https://leetcode.cn/problems/palindrome-partitioning/
算法思想：
采用回溯的思想。用startindex表示分隔的起始位置，i表示分隔的终止位置，判断起始位置到终止位置区间的字符是否是回文，是则加入，否则continue。
代码：
class Solution {
public:
vector<vector<string>> final;
vector<string> path;
bool judge(string s, int start, int end)
{
while(start<=end)
{
if(s[start]!=s[end])
return false;
start++;
end--;
}
return true;
}
void huisu(string s, int startindex)
{
if(startindex>=s.size())
{
final.push_back(path);
return;
}
for(int i=startindex;i<s.size();i++)
{
// cout<<"i:"<<i<<endl;
bool res = judge(s, startindex,i);
if(res==false)
continue;
path.push_back(s.substr(startindex, i-startindex+1));
huisu(s, i+1);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
huisu(s,0);
return final;
}
};
