class Solution {
public:vector<vector<int>> res;vector<int> path;int sum=0;void backtracking(vector<int>& candidates, int target,int startIndex){if(sum>target)return;if(sum==target){res.push_back(path);return;}for(int i=startIndex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0);return res;}
};首先我们要明白集合的概念 不论顺序 只要元素不一样就是组合 所以我们从小向大下标遍历 避免出现重复组合 这时候因为元素可以无限使用 每次下标不用加一
class Solution {
public:int sum=0;vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates, int target,int startIndex,vector<bool>& used){if(sum>target)return;if(sum==target){res.push_back(path);return;}for(int i=startIndex;i<candidates.size();i++){//如何判断当前结点相同数值之前是否已经被遍历过if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)continue;used[i]=true;sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i+1,used);used[i]=false;sum-=candidates[i];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,used);return res;}
};上一题：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
这一题：
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
我们可以看出和前一题不同在于candidates元素可能重复 candidate的元素在每个组合只能使用一次
如果没有重复元素 只要startIndex（i）+1就可以， 但如果有重复元素就说明即使每次startIndex（i）+1 后面的重复元素 比如两个 1 1 2 3 要生成 6 可能会生成两个 123 123 如何避免这种情况就是要在重复元素出现的时候避免重复遍历 后面的1可以看作前面的1的真子集 所有情况都是包含的
所以只要遍历第一个重复元素就行 ，所以每次看前一个元素是否相等并且有没有被遍历到
使用bool数组 注意一条路径可以前后元素可以相同 同一层不能相同 所以true代表递归 false代表回溯 得证
class Solution {
public:vector<vector<string>> res;vector<string> path;bool ishuiwen(string s){int i=0,j=s.size()-1;while(i<j){if(s[i]!=s[j])return false;i++;j--;}return true;}void backtracking(string s,int startIndex){if(startIndex>=s.size()){res.push_back(path);return;}for(int i=startIndex;i<s.size();i++){//从startINdex分隔string str=s.substr(startIndex,i-startIndex+1);if(ishuiwen(str)){path.push_back(str);}else{continue;}backtracking(s,i+1);path.pop_back(); }}vector<vector<string>> partition(string s) {backtracking(s,0);return res;}
};分隔回文串
首先遍历切割位置 利用substr切割字符串
递归直到start超范围说明成功找到一组 注意 不要先都递归在判断 判断过程相当于剪枝直接淘汰重复情况。