桥头网站建设,沈阳网页设计课,免费在线观看电影网站,上海网站建设不好2023.7.19 此题为 组合总和 的升级版。本题的特殊之处在于 给定的candidates数组只一个无序且包含重复元素的数组#xff0c;并且最终的解集不能包含重复的组合。 所以本题的关键在于去重。那么#xff0c;此类题的去重分为两种#xff0c;一种是解集内部去重#xff0c;灵…2023.7.19 此题为 组合总和 的升级版。本题的特殊之处在于 给定的candidates数组只一个无序且包含重复元素的数组并且最终的解集不能包含重复的组合。 所以本题的关键在于去重。那么此类题的去重分为两种一种是解集内部去重灵一种是解集之间的去重。 解集内部去重指不允许存在诸如{116}的解集本题题意说了candidates中的每个数字在每个组合中只能使用一次所以解集内部是需要去重的去重方法在组合总和已经使用过即在递归的时候将start_index1即可。有人可能会问示例中输出为什么有解集{116} 那是因为candidates数组本身就存在重复的元素也就是说两个1其实不是同一个1。 解集之间去重指不允许存在{116}和{161}这样的重复解集于是代码之中需要加一条去重的判断逻辑。 如果把回溯过程想象成树的话那么解集之间去重就是指树的横切面不能有相同的元素。下面直接看代码
class Solution {
public:vectorvectorint ans;vectorint path;void backtrating(vectorint candidates,int target,int sum,int start_index){if(sum target){ans.push_back(path);return;}if(sum target) return;for(int istart_index; icandidates.size(); i){if(istart_index candidates[i]candidates[i-1]) continue;//解集间去重path.push_back(candidates[i]);sum candidates[i];backtrating(candidates,target,sum,i1);//解集内部去重sum - candidates[i];path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());backtrating(candidates,target,0,0);return ans;}
}; 2023.7.23 也可以定义一个used数组判别当前元素是否在树枝上使用过如果没有那么就在树层上产生重复元素看代码
class Solution {
public:vectorvectorint ans;vectorint path;void backtrating(vectorint candidates,int target,int sum,int start_index,vectorboolused){if(sum target){ans.push_back(path);return;}if(sum target) return;for(int istart_index; icandidates.size(); i){//if(istart_index candidates[i]candidates[i-1]) continue;//树层去重if(i0 candidates[i]candidates[i-1] used[i-1]false) continue;used[i]true;path.push_back(candidates[i]);sum candidates[i];backtrating(candidates,target,sum,i1,used);sum - candidates[i];path.pop_back();used[i]false;}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());vectorbool used(candidates.size(),false);backtrating(candidates,target,0,0,used);return ans;}
}; 这种方式效率低一点但是更好理解。
