0%

LeetCode-40-组合总和II

LeetCode 40 组合总和II

40.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

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

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

回溯递归+跳过重复元素

相较于 39.组合总和,本题的主要区别在于, candidates 数组中的元素是重复的,并且存在特殊情况: 对于 [10,1,2,7,6,1,5] 从中组合8,存在特殊的重复问题,对于两个编号1都能够组成 [1,7] 但是在结果中将会被判定为重复。

此处修改的重点在于,选取 cur 并且完成递归后回溯时,那么在后序的递归需要跳过相同的元素。在总体的for循环内添加一个新的for循环,让其能够跳过相同元素,并且此处还需要着重判断数组越界问题:

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
class Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
void DFS(vector<int> &candidates,int target,int cur){
if(target==0){
res.push_back(tmp);
return;
}
if(target<0||cur>=candidates.size()||candidates[cur]>target) return;
for(int i=cur;i<candidates.size();){
tmp.push_back(candidates[i]);
target-=candidates[i];
DFS(candidates,target,i+1);
target+=candidates[i];
tmp.pop_back();
for(int a=candidates[i];i<candidates.size()&&a==candidates[i];i++);
// 在选取完元素后回溯,那么回溯的处理就是不选取当前元素,为了防止重复,跳过与当前元素相同的元素
if(i>=candidates.size()) return;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
DFS(candidates,target,0);
return res;
}
};

另一种跳过的实现:使用一个map对重复的数字个数进行统计(这样做将会导致空间复杂度的上升,当数据量巨大时将会导致大量的内存占用),对于当数值 cur 一次处理完全部的选取情况,假设当前数值 cur 总共有n个,那么分别尝试选取 0-n个的选取方式进行递归,当 cur 移动到下一个位置时必然不存在重复元素。

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
class Solution {
private:
vector<pair<int, int>> freq;
vector<vector<int>> ans;
vector<int> sequence;

public:
void dfs(int pos, int rest) {
if (rest == 0) {
ans.push_back(sequence);
return;
}
if (pos == freq.size() || rest < freq[pos].first) {
return;
}

dfs(pos + 1, rest);

int most = min(rest / freq[pos].first, freq[pos].second); // 使用min处理进行剪枝
for (int i = 1; i <= most; ++i) {
sequence.push_back(freq[pos].first);
dfs(pos + 1, rest - i * freq[pos].first);
}
for (int i = 1; i <= most; ++i) { // 最终必然是尝试了most个,全部回溯
sequence.pop_back();
}
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
for (int num: candidates) {
if (freq.empty() || num != freq.back().first) {
freq.emplace_back(num, 1);
} else {
++freq.back().second;
}
}
dfs(0, target);
return ans;
}
};
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道