LeetCode 40. 组合总和 II
题目描述
题意分析
从
candidates中选出若干元素，使它们的和恰好等于target，返回所有不同的组合。每个输入下标最多使用一次，但不同下标上的相同数值可以同时选中，不能把输入数组直接去重。组合不区分元素的排列顺序；选出的数值及各自出现次数相同，就属于同一个答案。候选值和目标值都是正整数，这保证继续选择只会让总和增大，也为超过目标时停止搜索提供了依据。
解法：排序后回溯去重
核心思路
[!blue]
先排序，再用
path保存已选元素，remain表示距离目标还差多少，start表示下一项允许选择的最小下标。选中下标i后递归到i + 1，这样同一下标不会复用，且每种下标组合只按递增顺序生成，不会因排列顺序不同重复搜索。不同下标仍可能对应相同值，因此还需要去掉数值重复。同一层的所有选择拥有相同的
path和remain，如果先后选择两个相等候选作为下一项，就会产生相同的数值分支。保留这一层的第一个相等值即可，其后满足i > start && candidates[i] == candidates[i - 1]的候选都跳过。这样不会漏掉需要多个同值元素的组合：先选较早的相等元素，下一层仍可选择后面的相等元素。对于同一层中较晚的相等值，它后面能组成的任何方案，较早的相等值都能配合同样的后缀组成，因此跳过较晚者不会损失新答案。
条件中的
i > start限定了只在同层去重。下一层的首个候选即使与前一层选中的值相等，也必须允许使用；把条件写成i > 0会错误地禁止一条路径使用多个同值元素。当
remain == 0时，复制当前路径加入答案并返回。若当前候选已经大于remain，排序保证后面的数只会更大，而所有数都为正，继续选不可能凑回目标，可以直接结束本层循环。其他候选则按“选择、递归、撤销”的顺序搜索，恢复路径后再尝试下一项。
解题步骤
- 将数组升序排序，使重复值相邻，并为
break剪枝提供单调性。- 定义
dfs(start, remain)：只从[start, n)选择下一项；remain == 0时复制path加入答案。- 本层遇到与前一个候选相同的值时跳过，但必须满足
i > start，否则会误删跨层的合法重复值。- 若
candidates[i] > remain，后续数字只会更大，直接break。- 选择
candidates[i]后递归dfs(i + 1, remain - candidates[i])，返回时撤销选择。
代码实现
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
dfs(candidates, target, 0, new ArrayList<>(), res);
return res;
}
private void dfs(
int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> res) {
if (remain == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// 只去掉同层的相等选择，更深一层仍可使用另一个相等元素。
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remain) {
break;
}
path.add(candidates[i]);
// 下一层越过当前下标，保证每个输入位置至多使用一次。
dfs(candidates, remain - candidates[i], i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
import "sort"
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
res := make([][]int, 0)
path := make([]int, 0)
var dfs func(int, int)
dfs = func(start int, remain int) {
if remain == 0 {
combo := append([]int(nil), path...)
res = append(res, combo)
return
}
for i := start; i < len(candidates); i++ {
// 只去掉同层的相等选择，更深一层仍可使用另一个相等元素。
if i > start && candidates[i] == candidates[i-1] {
continue
}
if candidates[i] > remain {
break
}
path = append(path, candidates[i])
// 下一层越过当前下标，保证每个输入位置至多使用一次。
dfs(i+1, remain-candidates[i])
path = path[:len(path)-1]
}
}
dfs(0, target)
return res
}
复杂度分析
- 时间复杂度：排序为 $O(n \log n)$；搜索树最多有 $O(2^n)$ 个节点。若把复制答案的成本计入，设所有答案的元素总数为 $S$，总时间为 $O(n \log n + 2^n + S)$，最坏可写作 $O(n \cdot 2^n)$。
- 空间复杂度：$O(n)$，来自递归栈与当前路径；不计返回结果本身。
关键点总结
[!green]
- 去重条件是
i > start && candidates[i] == candidates[i - 1]：同层去重，跨层放行。- 下一层传
i + 1控制「每个下标只用一次」；第 39 题可复用元素，传的是i。- 排序同时服务于相邻去重和正数剪枝，缺一不可。
- 收集答案时必须复制
path，因为回溯会继续修改原列表。
易错点总结
[!yellow]
- 把条件写成
i > 0：会跳过深层递归中允许使用的另一个相等元素，漏掉含多个同值元素的组合。- 递归仍传
i：会让同一个输入位置被反复选择；本题必须传i + 1，越过已选位置。- 答案不复制路径：直接加入
path后，后续回溯会把已经保存的答案一起修改。- 未排序就去重或剪枝：重复值可能不相邻，
break也不再安全。- 把同层去重的
continue写成break：当前值重复不代表更大的候选也无效，应跳过这个候选后继续枚举。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 39. 组合总和 | 中等 | 原题候选可重复取，本题一个下标最多取一次，递归起点需前进。 |
| 90. 子集 II | 中等 | 同样对排序后的重复值做同层去重，本题再增加目标和条件。 |
| 216. 组合总和 III | 中等 | 在选择和撤销之间枚举组合；本题候选只能用一次且需去重，该题固定元素数量且只取一到九。 |
| 77. 组合 | 中等 | 在选择和撤销之间枚举组合；本题候选只能用一次且需去重，该题只约束选择数量。 |
| 78. 子集 | 中等 | 在选择和撤销之间枚举组合；本题候选只能用一次且需去重，该题输出所有选择长度的子集。 |
| 377. 组合总和 Ⅳ | 中等 | 组合总和系列。II 每个输入位置只用一次并枚举无序组合；IV 允许重复取数并统计有序方案。 |