LeetCode 39：组合总和——Java DFS 回溯与剪枝详解

一、题目描述

给定一个无重复元素的正整数数组 candidates 和一个目标整数 target，找出所有数字之和等于 target 的不同组合。

数组中的同一个数字可以被重复选择。如果至少有一个数字的选择次数不同，就认为是不同组合。题目允许以任意顺序返回答案。

例如：

输入：candidates = [2, 3, 6, 7], target = 7
输出：[[2, 2, 3], [7]]

数字 2 可以重复使用，因此可以得到组合 [2,2,3]；数字 7 本身也等于目标值，所以 [7] 也是一个有效组合。

这道题的难点主要有两个：

• 同一个数字可以无限次使用；

• [2,2,3] 和 [3,2,2] 只能算作一种组合。

解决这两个问题的关键，就是 DFS、回溯和 start 起始下标。

二、把组合过程看成一棵决策树

假设：

candidates = [3, 4, 5], target = 9

从空组合开始，第一轮可以选择 3、4 或 5。选择一个数字后，再继续选择下一个数字，直到当前总和等于或者超过 target。

例如，先选择 3，当前路径为 [3]，总和为 3。因为数字可以重复使用，下一层仍然可以选择 3，得到 [3,3]；继续选择 3 后得到 [3,3,3]，总和正好为 9，因此找到一个有效组合。

如果先选择 4，再选择 5，可以得到 [4,5]。但如果第一轮选择 5，第二轮再选择 4，就会得到 [5,4]。两者包含的数字和数量完全相同，本质上是同一种组合，不能重复加入答案。

因此，我们不能让每一层都从数组下标 0 开始遍历，而要通过一个 start 参数控制下一层的选择范围。

三、start 如何避免重复组合

start 表示当前这一层可以从 candidates 的哪个位置开始选择。

for (int i = start; i < candidates.length; i++) {
// 选择 candidates[i]
}

假设当前第一次选择的是下标 1 对应的数字 4，那么后续只能继续选择下标大于或等于 1 的数字，即 4 和 5，不能再回头选择下标 0 的数字 3。

这样一来，可以生成 [4,5]，但不会再生成顺序相反的 [5,4]。所有组合都会按照候选数组中的下标顺序构造，从而自然避免重复。

这里要区分两个容易混淆的概念：

• start 限制的是当前层可以选择的起点，用来避免不同排列产生重复组合；

• 递归时传入 i，而不是 i + 1，用来允许当前数字被重复使用。

核心递归调用如下：

traverseTree(candidates, target, i);

如果传入 i + 1，当前数字在下一层就不能再次被选择，这将变成“每个数字最多使用一次”的另一类组合问题。

可以把这条规律记成一句话：

start 负责去重，传入 i 负责复用。

四、递归终止条件与剪枝

搜索过程中需要根据当前路径总和 sum 判断是否继续递归。

1. 找到有效组合

当 sum == target 时，说明当前路径是一组有效答案：

if (sum == target) {
res.add(new ArrayList<>(route));
return;
}

这里必须创建一个新的 ArrayList，保存当前路径的快照。不能直接将 route 放入结果集，因为 route 在后续回溯过程中还会继续修改。

2. 当前总和超过目标值

当 sum > target 时，可以直接结束当前分支：

if (sum > target) {
return;
}

题目保证候选数字都是正整数。总和一旦超过 target，继续添加数字只会使总和更大，当前分支不可能再得到有效答案，因此可以提前剪枝。

例如目标值为 9，当前路径为 [5,5]，总和已经是 10，就没有继续搜索的必要。

五、回溯的完整过程

在每一层递归中，需要完成“选择、递归、撤销选择”三个动作：

route.add(candidates[i]);
sum += candidates[i];

traverseTree(candidates, target, i);

route.removeLast();
sum -= candidates[i];

先把当前数字加入路径并更新总和，然后进入下一层继续搜索。递归返回后，删除刚刚加入的数字，同时恢复 sum，让程序回到选择该数字之前的状态，再尝试同一层的其他候选数字。

例如搜索 [3,3,3] 并记录答案后，需要依次回退到 [3,3]、[3]。只有恢复原来的路径和总和，才能继续尝试 [3,3,4]、[3,4] 等其他分支。

如果只删除路径末尾元素，却没有恢复 sum，路径和总和就会不一致，后面的判断也会全部出错。

六、完整 Java 代码

下面的实现与上述思路一致：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
// 保存所有符合条件的组合
private final List<List<Integer>> res = new LinkedList<>();

// 保存当前搜索路径
private final LinkedList<Integer> route = new LinkedList<>();

// 当前路径中所有数字之和
private int sum = 0;

public List<List<Integer>> combinationSum(int[] candidates, int target) {
traverseTree(candidates, target, 0);
return res;
}

private void traverseTree(int[] candidates, int target, int start) {
// 当前路径正好满足要求
if (sum == target) {
res.add(new ArrayList<>(route));
return;
}

// 数组元素均为正数，超过目标值后无法再恢复
if (sum > target) {
return;
}

// 只从 start 开始选择，避免产生重复排列
for (int i = start; i < candidates.length; i++) {
// 做出选择
route.add(candidates[i]);
sum += candidates[i];

// 仍从 i 开始，允许 candidates[i] 被重复选择
traverseTree(candidates, target, i);

// 撤销选择，恢复进入递归前的状态
route.removeLast();
sum -= candidates[i];
}
}
}

七、示例执行过程

以 candidates = [2,3,6,7]、target = 7 为例。

搜索首先从 2 开始：

[] → [2] → [2,2] → [2,2,2]

在 [2,2] 的基础上选择 3，得到 [2,2,3]，总和等于 7，记录答案。回溯后继续尝试其他数字，超过 7 的分支会直接返回。

当第一层选择 3 时，后续只能继续选择 3、6、7，不能再回头选择 2，因此不会生成 [3,2,2]。最后第一层选择 7，得到第二个有效组合 [7]。

最终结果为：

[[2, 2, 3], [7]]

八、复杂度分析

回溯算法需要枚举可能的组合，时间复杂度与候选数字及目标值有关。若最小候选数字为 m，决策树最大深度约为 target / m，最坏情况下搜索规模呈指数级增长，可粗略理解为 O(n^(target/m))。

空间复杂度主要来自递归调用栈和当前路径，最大递归深度约为 target / m，因此额外空间复杂度为 O(target/m)，不计算最终答案占用的空间。

九、常见错误

1. 每层都从零开始遍历

这样会同时产生 [2,2,3] 和 [3,2,2]，造成组合重复。应当使用 start 控制选择范围。

2. 递归时传入 i + 1

这会导致同一个数字无法重复使用，漏掉 [2,2,3] 这样的答案。本题应当继续传入 i。

3. 直接把 route 加入结果集

route 是一个不断变化的对象，必须使用 new ArrayList<>(route) 保存路径快照。

4. 递归后忘记恢复状态

回溯时既要删除末尾数字，也要减去该数字，使 route 和 sum 同时恢复。

5. 忽略剪枝成立的前提

sum > target 后能够直接返回，是因为题目中的候选数字都是正整数。如果允许负数，就不能使用这一剪枝逻辑。

十、总结

组合总和是一道典型的回溯题。我们通过 DFS 枚举所有可能的选择，使用 route 维护当前组合，使用 sum 判断当前状态，并在递归返回后撤销选择。

本题最关键的是 start 参数：同一层只从 start 之后选择，可以避免不同顺序产生重复组合；递归时继续传入当前下标 i，又能允许同一个数字被重复使用。当总和超过目标值时，再利用正整数条件提前剪枝。