LeetCode 39. 组合总和
题目描述
✅ 39. 组合总和
题意分析
从互不相同的正整数候选值中选择若干个数，使总和等于
target，返回所有不同的组合。每个候选值可以使用任意多次，但组合只关心各个数用了多少次，不区分先后顺序。需要同时解决两个问题：允许重复使用同一个值，又不能把同一组数的不同排列重复加入答案。可以规定组合中的选择下标始终不下降，既允许停在当前下标继续选择，又禁止回头产生排列式重复。
候选值都是正数，所以每选一个数，剩余目标都会严格减小。这既保证搜索能够结束，也允许在候选值超过剩余目标时剪掉这一分支。下面先对候选数组排序，会改变输入数组的顺序。
解法：排序后回溯枚举组合
核心思路
[!blue]
回溯状态由三部分组成：
path保存已经选择的数，remain表示距离目标还差多少，start表示接下来允许选择的最小下标。始终保持路径元素之和加上remain等于原目标，从空路径、完整目标和下标0开始。每层从
start开始枚举候选i。选择它后，把它加入路径，并用remain - candidates[i]进入下一层；下一层起点仍传i，允许再次使用当前值。由于不再选择更小的下标，路径中的下标不会下降。每个合法组合都能唯一地按下标非递减排列，这种选择顺序一定会被递归枚举到；不同排列则被起点限制排除。候选值本身互不相同，所以无需额外去重集合，也不需要像含重复输入的组合题那样跳过同层相等值。
先升序排序后，如果
candidates[i] > remain，不但当前值不能选，后面的值也都不能选，因此直接结束本层循环。正数意味着后续继续添加只会让总和更大，无法修复超出的部分；只选择不超过remain的值，也使递归中的剩余目标始终非负。当
remain == 0，当前路径恰好构成答案，复制一份保存后立即返回，不再追加正数。每次递归返回后，都删除本轮加入的末尾元素，恢复父层路径，再尝试其他候选；副本则保留已找到答案的内容，不受后续撤销影响。
解题步骤
- 将候选数组升序排序，初始化空路径与结果集。
- 从
start = 0、remain = target开始回溯。- 若
remain == 0，复制路径加入结果，结束当前递归。- 否则从
start枚举下标i；如果候选值大于remain，直接结束本层循环。- 将候选加入路径，递归传入同一个下标
i和减少后的剩余目标。- 返回后撤销路径末尾元素，继续本层下一个候选。
代码实现
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(
int[] candidates,
int remain,
int start,
List<Integer> path,
List<List<Integer>> result) {
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// 数组已排序，当前值过大时后面的候选也都不可用。
if (candidates[i] > remain) {
break;
}
path.add(candidates[i]);
// 继续传当前下标，允许同一数字重复使用。
backtrack(candidates, remain - candidates[i], i, path, result);
path.remove(path.size() - 1);
}
}
}
import "sort"
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
result := make([][]int, 0)
path := make([]int, 0)
var backtrack func(int, int)
backtrack = func(start, remain int) {
if remain == 0 {
result = append(result, append([]int(nil), path...))
return
}
for i := start; i < len(candidates); i++ {
// 数组已排序，当前值过大时后面的候选也都不可用。
if candidates[i] > remain {
break
}
path = append(path, candidates[i])
// 继续传当前下标，允许同一数字重复使用。
backtrack(i, remain-candidates[i])
path = path[:len(path)-1]
}
}
backtrack(0, target)
return result
}
复杂度分析
- 时间复杂度：$O(n \log n + S + Rd)$，
n为候选个数，S为实际搜索树节点数，R为答案数，d = \lfloor target / \min(candidates) \rfloor为路径长度上界。排序后，每次可行选择产生一个子节点，每层最多额外检查一个过大的候选，保存答案还需要复制路径；最坏搜索规模为指数级。- 空间复杂度：辅助空间为 $O(d + \log n)$，来自回溯路径、递归栈与排序栈；返回结果最多另外占用 $O(Rd)$ 空间。
关键点总结
[!green]
start保证组合按固定顺序生成，避免排列重复。- 递归传
i表示当前数字可以继续使用。- 排序后才能在候选值过大时用
break剪枝。- 保存答案时必须复制当前路径。
易错点总结
[!yellow]
- 递归传
i + 1会让每个数字只能使用一次。- 每层都从下标
0开始会生成重复组合。- 忘记撤销选择会污染后续分支。
- 直接保存
path引用，后续回溯会改坏已经记录的答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 40. 组合总和 II | 中等 | 同样搜索目标和组合，原题每个输入位置只能用一次且可能有重复，本题允许同一候选反复选择。 |
| 377. 组合总和 Ⅳ | 中等 | 同样由候选组成目标和，原题把不同排列顺序视为不同方案，本题不区分顺序。 |
| 216. 组合总和 III | 中等 | 在选择和撤销之间枚举组合；本题允许同一候选被多次选取，该题固定元素数量且只取一到九。 |
| 77. 组合 | 中等 | 在选择和撤销之间枚举组合；本题允许同一候选被多次选取，该题只约束选择数量。 |
| 78. 子集 | 中等 | 在选择和撤销之间枚举组合；本题允许同一候选被多次选取，该题输出所有选择长度的子集。 |