建网站定制,wordpress登录验证,wordpress 用什么服务器配置,新沂建设网站原题出于leetcode第40题https://leetcode.cn/problems/combination-sum-ii/题目如下#xff1a;
给定一个候选人编号的集合 candidates #xff08;candidate中有重复的元素#xff09;和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合…原题出于leetcode第40题https://leetcode.cn/problems/combination-sum-ii/题目如下
给定一个候选人编号的集合 candidates candidate中有重复的元素和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合
1树型结构 这里引入两个概念——树枝去重和树层去重因为元素不可重复读取且不能有重复组合因此我们只需处理树层去重如上图所示。去重代码如下
if(i0 candidate[i]candidate[i-1] used[i-1]0) continue;
2代码
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint candidates,int target,int sum,int startindex,vectorbool used){if(sumtarget) return ;if(sumtarget){result.push_back(path); return; }for(int istartindex;icandidates.size();i){if(i0 candidates[i]candidates[i-1] used[i-1]0)continue;sumcandidates[i];path.push_back(candidates[i]);used[i]true;backtracking(candidates,target,sum,i1,used);sum-candidates[i];path.pop_back();used[i]false;}return ;}vectorvectorint combinationSum2(vectorint candidates, int target) {int ncandidates.size();vectorboolused(n,0);path.clear();result.clear();sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used); return result; }
}; 以上树型结构的图片出自代码随想录
