【LetMeFly】40.组合总和 II：回溯 + 剪枝
力扣题目链接：https://leetcode.cn/problems/combination-sum-ii/
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
解题方法：回溯（剪枝）
类似39.组合总和：回溯 + 剪枝，但这道题比较困难的地方在于，candidates中有重复的元素，而答案中不能有重复的数组。
怎么办呢，排序呗。刚开始还和之前一样走正常流程：
- 如果target已经达到则将当前方案加入答案数组。
- 如果已超target则直接返回
- 选当前元素并回溯
- 不选当前元素
不同之处在于，不选当前元素时，要保证选择的下一个元素和当前元素不同。
例如[4, 4, 5]，不选第一个4的话，就不能选第二个4。
否则的话，可能会出现第一个4和5、第二个4和5这两种相同的方案。
- 时间复杂度$O(len(candidates)^2)$
- 空间复杂度$O(len(candidates))$
AC代码
C++
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
|
class Solution {
private:
vector<vector<int>> ans;
vector<int> now;
void dfs(vector<int>& c, int target, int index) {
if (!target) {
ans.push_back(now);
return;
}
if (index == c.size() || target < 0) {
return;
}
now.push_back(c[index]);
dfs(c, target - c[index], index + 1);
now.pop_back();
int next = index;
while (++next < c.size() && c[next] == c[index]);
dfs(c, target, next);
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0);
return ans;
}
};
|
Python
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
| '''
Author: LetMeFly
Date: 2025-01-26 07:58:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-26 08:01:59
'''
from typing import List
class Solution:
def dfs(self, target: int, index: int) -> None:
if not target:
self.ans.append([i for i in self.now])
return
if index == len(self.c) or target < 0:
return
self.now.append(self.c[index])
self.dfs(target - self.c[index], index + 1)
self.now.pop()
next = index + 1
while next < len(self.c) and self.c[next] == self.c[index]:
next += 1
self.dfs(target, next)
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
self.c = candidates
self.ans = []
self.now = []
self.dfs(target, 0)
return self.ans
|
Java
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
|
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
private List<List<Integer>> ans;
private List<Integer> now;
private int[] c;
private void dfs(int target, int index) {
if (target == 0) {
ans.add(new ArrayList<>(now));
return;
}
if (index == c.length || target < 0) {
return;
}
now.add(c[index]);
dfs(target - c[index], index + 1);
now.remove(now.size() - 1);
int next = index;
while (++next < c.length && c[next] == c[index]);
dfs(target, next);
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
c = candidates;
ans = new ArrayList<>();
now = new ArrayList<>();
dfs(target, 0);
return ans;
}
}
|
Go
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
|
package main
import "sort"
func dfs(c []int, target int, now []int, index int, ans *[][]int) {
if target == 0 {
*ans = append(*ans, append([]int{}, now...))
return
}
if index == len(c) || target < 0 {
return
}
now = append(now, c[index])
dfs(c, target - c[index], now, index + 1, ans)
now = now[:len(now) - 1]
next := index + 1
for next < len(c) && c[next] == c[index] {
next++
}
dfs(c, target, now, next, ans)
}
func combinationSum2(candidates []int, target int) (ans [][]int) {
var now []int
sort.Ints(candidates)
dfs(candidates, target, now, 0, &ans)
return
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/145363298