leetcode第40题组合总和Ⅱ

原题出于leetcode第40题 leetcode /problems/combination-sum-ii/题目如下：

给定一个候选人编号的集合 candidates （candidate中有重复的元素）和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合

1树型结构

这里引入两个概念——树枝去重和树层去重，因为元素不可重复读取且不能有重复组合，因此我们只需处理树层去重，如上图所示。去重代码如下：

if(i>0 && candidate[i]==candidate[i-1] && used[i-1]==0) continue; 2代码 class Solution { public: vector<int> path; vector<vector<int>> result; void backtracking(vector<int>& candidates,int target,int sum,int startindex,vector<bool>& used) { if(sum>target) return ; if(sum==target) { result.push_back(path); return; } for(int i=startindex;i<candidates.size();i++) { if(i>0 &&candidates[i]==candidates[i-1]&& used[i-1]==0) continue; sum+=candidates[i]; path.push_back(candidates[i]); used[i]=true; backtracking(candidates,target,sum,i+1,used); sum-=candidates[i]; path.pop_back(); used[i]=false; } return ; } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { int n=candidates.size(); vector<bool>used(n,0); path.clear(); result.clear(); sort(candidates.begin(),candidates.end()); backtracking(candidates,target,0,0,used); return result; } };

以上树型结构的图片出自代码随想录