5.组合总和
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。
对比一下：
找出所有相加之和为
n的k个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
其实我觉得这两题挺像的，最大的区别就是第五题并没有k的限制，所以深度并未被限制
以及元素可以重复选用，所以backtracking(target,candidates,i)传入的应该是i而不是i+1，这样才能保证结果中可以出现重复元素的结果
class Solution {
public:vector<vector<int>>result;vector<int>path;void backtracking(vector<int>&candidates,int target,int sum,int startIndex){//终止条件if(sum>target)//一定加上这个判断，不然就会栈溢出{return;}if(sum==target){result.push_back(path);return;}for(int i = startIndex;i<candidates.size();i++)//注意本题的i是坐标{sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);path.pop_back();sum-=candidates[i];}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();backtracking(candidates,target,0,0);//startIndex在本题传入的是下标，所以从0开始return result;}
};6.组合总和II
给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。
这题更像了
找出所有相加之和为
n的k个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
最大的区别就是去重！
要求是不可在一个组合中使用用一个元素，但是可以用值相等的不同元素！
首先，我们在给backtracking传入数组时，我们不是传入原来的数组，而是将排序过后的数组传入 为什么呢？
示例：输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
如果直接操作原数组，那么在取第一个1的时候，我们会得到一次[1,7]，然后在取第二个1的时候，又会得到一次[1,7]就重复了
但是如果我们将数组进行排序，并引入一个bool类型的used数组，这个数组的长度与数组相同，每个位置的false代表这个位置对应的元素已经使用过，如果是true说明这个元素正在使用
排序后的数组：[1,1,2,5,6,7,10]起到将相邻的元素放到一起的作用
然后传入 backtracking()，当循环到第一个1时，将数组used[i]设为true，代表正在历经第一个1能组成的所有结果，遍历完就把used设回false
再循环到第二个1时，通过判断candidates[i]是否与candidates[i-1]相等 && used[i-1]是否为false，如果相等并且used[i-1]=false说明当前这个和前者相同的元素已经遍历完了所有它的可能值，不要再循环了
难点讲解完毕，上代码
class Solution {
public:vector<vector<int>>result;vector<int>path;void backtracking(vector<int>&candidates,int target,int sum,int startIndex,vector<bool>& used){//终止条件if(sum==target){result.push_back(path);return;}for(int i=startIndex;i<candidates.size()&& sum+candidates[i]<=target;i++){//注意：sum+candidates[i]<=target是剪枝操作if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false)//说明这个元素用过了{continue;}sum+=candidates[i];path.push_back(candidates[i]);used[i]=true;//正在使用backtracking(candidates,target,sum,i+1,used);used[i]=false;//用过了path.pop_back();//回溯sum-=candidates[i];//}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>used(candidates.size(),false);//设置used数组来管理使用过的元素result.clear();path.clear();sort(candidates.begin(),candidates.end());//难点，为什么要给数组排序backtracking(candidates,target,0,0,used);return result;}
};7.分割回文子串
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是回文串
。返回
s所有可能的分割方案。示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a" 输出：[["a"]]
上图是根据给的示例做的分割,不理解的话建议看卡哥的视频讲解，听完就感觉这题很简单了
套用回溯算法模板
void backtracking(参数) {if (终止条件) {存放结果;return;}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
class Solution {
public:vector<string>path;//存储每一组回文串的集合vector<vector<string>>result;//二维数组，存储最终结果bool isHuiWen(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;}
void backtracking(const string& s,int startIndex)//startIndex起到切割线的作用{//终止条件if(startIndex >= s.size())//说明已经切割到字符串最后{result.push_back(path);return;}for(int i = startIndex;i<s.size();i++){//startIndex是不变的，但是i是不断增加的//难点：要想到边循环边判断回文if(isHuiWen(s,startIndex,i)==true){//取子串string str = s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{continue;}backtracking(s,i+1);path.pop_back();//回溯弹出}}vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s,0);return result;}
};
时间复杂度O(n²)
