回溯算法
39. 组合总和
题意：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例：
思路：本题我们需要清楚组合数组可以有什么组成？
- 必须是已经给出的元素
- 元素可以重复，这就意味着可以重复递归很多次，例如：1，2等超小数字
根据组合数组的组成规范，我们可以得出回溯的终止条件：当数组大于等于目标值target时，必须返回，且等于目标值时保存并发返回。其次是回溯算法的具体过程：先将元素添加到组合中，然后继续添加相同的元素进去，直到组合大于等于目标值才返回，说明第一个元素组合结束，然后才引入下一个元素进行替换尝试
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
int ComTmp(vector<int> tmp)//计算数组的总和
{
int sum=0;
for(auto e:tmp)
{
sum+=e;
}
return sum;
}
void ComTarArr(vector<int>& candidates,int target,int begin)
{
if(ComTmp(tmp)>=target)//只要数组总和大于等于目标值都返回，因为组合的数组是没有明确要求的
{
if(ComTmp(tmp)==target)//但是只有等于目标值的数组才能保存
{
arr.push_back(tmp);
}
return;
}
for(int i=begin;i<candidates.size();i++)
{
tmp.push_back(candidates[i]);
ComTarArr(candidates,target,i);//这里没有++，是因为组合中可以使用重复的元素
tmp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
ComTarArr(candidates,target,0);
return arr;
}40. 组合总和 II
题意：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例：
思路：本题我们主要是在组合数组时就排除重复组合的情况，利用bool的数组标记同枝和同层被使用的元素，然后跳过这些被使用的元素；当我们存储tmp时，就说明这是一组未被保存的元素集合
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void ComTarArr(vector<int>& candidates,int target,int begin,int sum,vector<bool> block)//三个特殊变量，begin为加入元素下标，sum是组合数组总和，block是标记已经被使用的元素
{
if(sum==target)
{
arr.push_back(tmp);
return;
}
for(int i=begin;i<candidates.size()&&sum<=target;i++)
{
if(i>0&&candidates[i-1]==candidates[i]&&block[i-1]==false)//排除相同元素的情况和重复组合的情况，例如：1 7，7 1
{
continue;
}
sum+=candidates[i];
block[i]=true;//标记元素同枝被使用
tmp.push_back(candidates[i]);
ComTarArr(candidates,target,i+1,sum,block);
sum-=candidates[i];
block[i]=false;
tmp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> block(candidates.size(),false);
sort(candidates.begin(),candidates.end());
ComTarArr(candidates,target,0,0,block);
return arr;
}131. 分割回文串
题意：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
示例：
思路：本题大致思想是在组合时就判断出该组合是否都是回文字符串，然后在回溯终止时直接存储即可。
回溯过程中，先一个个元素截断，必然都是回文的组合，然后再通过回溯，将最后两个字符串结合判断是否回文，这样以此循环类推，即可得到整个组合顺序
C++代码：
vector<vector<string>> arr;
vector<string> tmp;
bool PalindStr(string s,int left,int right)//验证字符串是否回文
{
while(left<=right)
{
if(s[left]!=s[right])
{
return false;
}
left++,right--;
}
return true;
}
void DividStr(string s,int begin)
{
if(begin>=s.size())//开头已经走到字符串的末尾了，说明组合结束，需要保存
{
arr.push_back(tmp);
return;
}
for(int i=begin;i<s.size();i++)
{
if(PalindStr(s,begin,i))//先判断截断的字符串是否回文，回文才会加入
{
string ss=s.substr(begin,i-begin+1);
tmp.push_back(ss);
}
else//如果有一个字符串不是回文，那整个组合就不成立，就不会继续向下判断，直接跳过
{
continue;
}
DividStr(s,i+1);
tmp.pop_back();
}
}
vector<vector<string>> partition(string s) {
DividStr(s,0);
return arr;
}