leetcode第40题组合总和Ⅱ

原题出于leetcode第40题https://leetcode.cn/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;       }
};

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