回溯法：组合
睡不醒的鲤鱼 2021-12-09 每日一题 LeetCode
# 0039. 组合总和 (opens new window)
题目
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
依据每个位置的元素可选取的次数进行搜索。
代码
class Solution {
vector<vector<int>> ans;
vector<int> combine;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0);
return ans;
}
void dfs(vector<int>& candidates, int target, int idx) {
if (target == 0) {
ans.push_back(combine);
return;
}
if (idx == candidates.size()) return;
dfs(candidates, target, idx + 1);
if (target >= candidates[idx]) {
combine.push_back(candidates[idx]);
dfs(candidates, target - candidates[idx], idx);
combine.pop_back();
}
}
};
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 0040. 组合总和 II (opens new window)
题目
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
本题与 0039. 组合总和 的区别在于需要对结果去重，同时每个元素只能选取一次。
可以先将原数组排序，在搜索时通过判断重复元素的个数，那么对元素 c[i] 最多可以选个 k[i] 次，从而转换成上题的解法。
代码
class Solution {
vector<vector<int>> ans;
vector<int> combine;
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0);
return ans;
}
void dfs(vector<int>& candidates, int target, int idx) {
if (target == 0) {
ans.push_back(combine);
return;
}
if (idx == candidates.size()) return;
// 统计重复元素的个数
int cnt = 1;
while (idx + 1 < candidates.size() && candidates[idx] == candidates[idx + 1]) {
idx++, cnt++;
}
// 尝试重复选取当前元素
for (int i = 0; i <= cnt && target >= i * candidates[idx]; i++) {
dfs(candidates, target - i * candidates[idx], idx + 1);
combine.push_back(candidates[idx]);
}
// 恢复现场
for (int i = 0; i <= cnt && target >= i * candidates[idx]; i++) {
combine.pop_back();
}
}
};
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
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
# 0077. 组合 (opens new window)
题目
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
枚举每个位置可能出现的数字，由于要求的是组合数，不考虑元素顺序，因此还需要记录一个 start 参数，表示当前数字从几开始选择。
代码
class Solution {
vector<vector<int>> ans;
vector<int> cur;
public:
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
void dfs(int start, int n, int k) {
if (k == 0) {
ans.push_back(cur);
return;
}
for (int i = start; i <= n; i++) {
cur.push_back(i);
dfs(i + 1, n, k - 1);
cur.pop_back();
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 0216. 组合总和 III (opens new window)
题目
解析
代码
# 0254. 因子的组合 (opens new window)
题目
解析
代码
# 0377. 组合总和 Ⅳ (opens new window)
题目
解析
代码