题目简介：
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
1
2
3
4
5
6
7
8
| 输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
|
示例 2:
1
2
3
4
5
6
| 输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
|
思路：
依然是道回溯题，和 39. 组合总和 相比多了个去重的操作。
为了方便去重，我们先将数组排序，我们可以想象一下产生重复的操作出现在哪里？
如数组[1,1,7], target = 8时，若依次选了第一个和第二个1，就和7组成了两个重复的数组。
所以为了避免重复数组的产生，当i > 0 && candidates[i] == candidates[i - 1] && !visit[i - 1]时，直接continue跳过即可。(即第一个1已经把所有情况遍历完毕了，此时visit[0] = false，第二个1就直接不需要再遍历了)。
tip:
- 使用哈希表作为是否访问过的标志数组。(省去了初始化)
代码如下：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public:
vector<vector<int>> res;
unordered_map<int, bool> visit;
void dfs(vector<int>& candidates, int target, int pos, vector<int>& temp){
if(target < 0)
return;
if(target == 0){
res.push_back(temp);
return;
}
for(int i = pos; i < candidates.size(); i++){
if(i > 0 && candidates[i] == candidates[i - 1] && !visit[i - 1])
continue;
if(!visit[i]){
temp.push_back(candidates[i]);
visit[i] = true;
dfs(candidates, target - candidates[i], i + 1, temp);
temp.pop_back();
visit[i] = false;
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> temp;
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, temp);
return res;
}
};
|
