1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtrace(vector<int>& candidates, int target,int start,bool note) {
if (target == 0) {
result.push_back(path);
return;
}
if (target < 0) {
return;
}
for (int i = start; i < candidates.size(); i++) {
if(!note && i > 0 && candidates[i-1] == candidates[i]) continue;
path.push_back(candidates[i]);
target -= candidates[i];
backtrace(candidates, target, i + 1,true);
note = false;
path.pop_back();
target += candidates[i];
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
backtrace(candidates,target,0,false);
return result;
}
};
|
前面做的组合题，不管强调与否，我们都知道数组中的元素是没有重复的，但这道题恰恰相反。看来只要解决重复元素可能带来的问题就可以了。
首先需要对元素进行排序，这样益于跳过重复的元素，可以说必须做这一步。难道我们只需要判断 前后两个数据是否相同就能忽略重复的元素带来的问题吗？
1
| i > 0 && candidates[i-1] == candidates[i]
|
不是，因为进入 backtrace 中导致本来用来满足需求的元素被忽略，仔细看下面这个例子：
1
| candidates = {1，1，1，2，1}，target = 2
|
第一个元素和第二个元素可以组合，但是由于如上的判断条件导致忽略。造成这个的原因是，我们本意忽略的元素是处于同一层的相同元素，但是进入 backtrace 中的元素属于要和上一层元素进行组合的，不应该忽略。
那么我们就用一个布尔值 note 标记，如果 note 为 false 表明在同一层（同一个栈），否则在不同层（不同栈）。同层的元素相同可被忽略，不同层的元素相同不可被忽略。
