39.组合总和
思路
本题的前置条件很多，如无重复元素等等，这个题目很好做，与之前的组合问题不同的是可以无限制重复选取元素。
注意： 既然可以重复选取，每次递归不必后移，树层之间（for循环）自然终止条件没有了，要额外添加终止条件。
题解
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
int sum;
void backtracking(vector<int>& candidates, int target,int start)
{
if(target<0)return;
if(target == 0)
{
res.push_back(path);
return ;
}
for(int i = start;i<candidates.size();i++)
{
path.push_back(candidates[i]);
backtracking(candidates, target-candidates[i],i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates,target,0);
return res;
}
};
40.组合总和II
思路
去重思路：之前做过三数之和，知道要sort先给排个序，为何？组合重复是因为里面由相同元素，要跳过相同元素就要把他们放在一起，所以排序理所应当也必不可少。
去重图解：
去重中注意使用while，以及注意在条件中保证不要越界。
题解
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& candidates, int target,int start)
{
if(target<0)return;
if(target == 0)
{
res.push_back(path);
return ;
}
for(int i = start;i<candidates.size();i++)
{
path.push_back(candidates[i]);
backtracking(candidates, target-candidates[i],i+1);
while(i<candidates.size()-1 && candidates[i] == candidates[i+1])i++;
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
for(auto i:candidates)cout<<i;
backtracking(candidates, target, 0);
return res;
}
};
131.分割回文串
思路
读题读题再读题，题目要求是满足分割得到的字串都是回文串！
分割问题与组合问题类似，只不过把数组中的元素转变为了字符串中的边界。
从头手动画图理清思路极其重要，要不然很容易糊涂。
题解
class Solution {
public:
vector<string> part;
vector<vector<string>> res;
bool isagain(string s)
{
string s1 = s;
reverse(s.begin(), s.end());
if(s1 == s)return true;
else return false;
}
void backtrackint(string s)
{
if(s.empty())
{
res.push_back(part);
return;
}
for(int i = 1;i<=s.size();i++)
{
string temp(s.begin(),s.begin()+i);
if(isagain(temp))
{//必须得是回文串才能进一步操作
//必须得是回文串才有资格push，当然也才有资格pop
part.push_back(temp);
string temp1(s.begin()+i,s.end());
backtrackint(temp1);
part.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
backtrackint(s);
return res;
}
};