力扣-回溯-40组合总和Ⅱ

思路

需要实现树枝层面的去重，利用use数组来判别，如果前一个节点已经使用了，说明这是在往深处遍历了，允许重复，如果前一个节点没有使用且值相同的话，说明是在树枝上重复了

代码 class Solution { public: vector<int> path; vector<bool> used; vector< vector<int>> result; int curSum; void backtracking(vector<int>& candidates, int target, int startIndex){ if(curSum > target) return; if(curSum == 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]){ continue; } used[i] = true; path.push_back(candidates[i]); curSum += candidates[i]; backtracking(candidates, target, i+1); curSum -= candidates[i]; path.pop_back(); used[i] = false; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); for(int i = 0; i < candidates.size(); i++){ used.push_back(false); } backtracking(candidates, target, 0); return result; } };