LeetCode 39：组合总和（Combination Sum）题解

Combination Sum 是 LeetCode Hot 100 里面一道非常经典的回溯题。

这道题和前面的“电话号码的字母组合”“括号生成”一样，核心方法都是回溯；但它又有自己的特点： 不是单纯去枚举所有排列或者字符串，而是要在给定数组中不断选择数字，让它们的和恰好等于目标值 target。

也正因为如此，这道题非常适合拿来理解回溯中的几个核心概念：

• 路径是什么

• 选择是什么

• 为什么可以重复选择同一个元素

• 为什么排序后可以剪枝

你给出的这份 Java 代码，就是这道题最经典、最标准的一种写法。 它的核心思路就是：

排序 + 回溯 + 剪枝

本文就结合这段代码，系统地讲一下这道题的解法思路。

题目介绍

给你一个 无重复元素 的整数数组 candidates，以及一个目标值 target，要求你找出 candidates 中所有可以使数字和为 target 的组合。

注意这道题有两个非常重要的条件：

1. candidates 中的每个数字可以被 无限次重复选取

2. 返回的组合不能重复

例如：

candidates = [2,3,6,7], target = 7

那么合法的组合有：

[2,2,3]
[7]

因为：

• 2 + 2 + 3 = 7

• 7 = 7

而像 [3,2,2] 这种，其实和 [2,2,3] 本质是同一个组合，不应该重复出现在答案中。

所以这道题真正要做的，不只是“凑出 target”，还要保证：

结果不重不漏。

示例

示例 1

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

解释：

• 可以选 7 一次

• 也可以选 2、2、3

这两个组合都满足和为 7。

示例 2

输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]

这里可以看到，同一个数字可以被重复使用很多次，比如 2 可以选 4 次。

示例 3

输入：candidates = [2], target = 1
输出：[]

因为只有数字 2，而目标是 1，显然无法凑出来，所以结果为空。

为什么这道题适合用回溯？

因为这道题本质上就是一个“尝试所有可能组合”的过程。

假设我们当前还剩余一个目标值 target，那么每一步都可以从 candidates 中选一个数：

• 选了之后，目标值就减少

• 然后继续递归地去解决剩余目标值的问题

• 如果某一时刻刚好减到 0，说明当前路径是一组合法解

• 如果某个数已经比剩余目标值还大，那这条路就不可能成功了

这种“先做选择，再递归探索，最后回退恢复现场”的流程，就是标准的回溯模型。

你可以把它想象成一棵搜索树：

• 每一个结点表示当前已经选出来的一组数字

• 每往下一层，就表示再选一个数字

• 当路径和恰好等于目标值时，就得到一个答案

所以这道题天然就很适合回溯。

最朴素的想法是什么？

如果完全不考虑优化，一个很直接的想法可能是：

• 枚举所有可能的数字组合

• 计算它们的和

• 看看是否等于 target

但问题在于，数字可以重复选，这就会让搜索空间变得非常大。 而且如果不加控制，很容易生成很多顺序不同、但本质相同的重复组合。

比如：

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

这三种写法其实是同一个组合。

所以我们不仅要回溯，还要想办法在搜索过程中避免重复。

核心思路

这道题的标准做法可以概括成三点：

1. 先排序

先把数组排序，有两个好处：

• 方便后面剪枝

• 方便让组合按照固定顺序生成，从而避免重复

2. 回溯搜索

每次从某个起点 start 开始，尝试选择一个数字加入当前组合。

3. 控制搜索起点，避免重复

当我们在某一层选择了 candidates[i] 后，下一层递归仍然从 i 开始，而不是从 0 开始。 这样就保证了：

• 当前组合中的数字顺序始终非递减

• 不会出现 [2,3,2] 这种顺序打乱的重复结果

这一步非常关键。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
​
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 先排序，便于剪枝
        Arrays.sort(candidates);
​
        // 从下标 0 开始回溯
        backtrack(candidates, target, 0, new ArrayList<>());
        return result;
    }
​
    private void backtrack(int[] candidates, int target, int start, List<Integer> combination) {
        // 如果 target 恰好为 0，说明当前组合合法
        if (target == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }
​
        for (int i = start; i < candidates.length; i++) {
            // 剪枝：如果当前数已经大于 target，后面更大的数也不用看了
            if (candidates[i] > target) break;
​
            // 选择当前数字
            combination.add(candidates[i]);
​
            // 因为同一个数字可以重复使用，所以递归时仍然传 i
            backtrack(candidates, target - candidates[i], i, combination);
​
            // 撤销选择
            combination.remove(combination.size() - 1);
        }
    }
}

代码拆解

这段代码的结构非常标准，几乎就是回溯题模板。 下面一步一步来看。

1. 为什么先排序？

Arrays.sort(candidates);

排序在这道题里非常重要。

第一，方便剪枝

排序之后，数组从小到大排列。 如果当前枚举到某个数时发现：

candidates[i] > target

那么后面的数只会更大，也一定不可能再凑出目标值了。 这时就可以直接 break，不用继续往后搜。

第二，方便去重

排序之后，我们在回溯时始终从当前下标及其后面开始选，这样组合中的元素顺序天然是非递减的。 于是 [2,2,3] 会出现，而 [3,2,2] 不会出现。

这就避免了很多重复情况。

2. backtrack 里的参数分别表示什么？

private void backtrack(int[] candidates, int target, int start, List<Integer> combination)

这四个参数非常关键：

• candidates：候选数组

• target：当前还剩多少值需要凑

• start：本轮搜索从哪个下标开始

• combination：当前已经选出来的组合

也就是说，这个函数表示的是：

在当前路径 combination 的基础上，从 start 开始继续选择数字，看看能不能把剩余目标值 target 凑出来。

只要把这个定义理解清楚，后面的递归就不容易乱。

3. 为什么 target == 0 时就加入答案？

if (target == 0) {
    result.add(new ArrayList<>(combination));
    return;
}

因为这说明当前路径中数字的和刚好等于目标值。

这时候 combination 就是一组合法答案，应该加入结果集。

注意这里一定要写成：

new ArrayList<>(combination)

而不能直接把 combination 本身放进去。

因为 combination 是一个会不断修改的路径对象，如果直接放引用，后面回溯删除元素时，结果集里的内容也会跟着变。

所以这里必须拷贝一份当前路径。

4. 为什么循环从 start 开始？

for (int i = start; i < candidates.length; i++)

这一步是避免重复的核心。

比如当前我们已经选了一个 2，接下来还可以继续选：

• 2

• 3

• 6

• 7

但没必要再回头去选比当前更靠前的数字，因为那样只会生成顺序不同、但本质相同的组合。

所以我们规定：

后续递归只能从当前下标 start 及其后面继续选择。

这样就能保证组合中的数字顺序始终是固定的，从而避免重复答案。

5. 为什么 candidates[i] > target 时可以直接 break？

if (candidates[i] > target) break;

因为数组已经排序。

如果当前数都已经比剩余目标值大了，那后面的数只会更大，更不可能满足要求。

例如：

candidates = [2,3,5,7]
target = 4

当你枚举到 5 时，就可以直接停止，因为 5、7 都不可能参与当前组合。

这就是剪枝。 它可以有效减少很多无意义的搜索。

6. 为什么递归时传的是 i，而不是 i + 1？

backtrack(candidates, target - candidates[i], i, combination);

这是这道题非常重要的一个细节。

因为题目明确说了：

同一个数字可以被无限次重复选取。

所以当你当前选了 candidates[i] 之后，下一层仍然可以继续选它自己。 这就是为什么递归时仍然传 i。

如果这里写成：

i + 1

那就变成“每个数字只能选一次”了，那是另一道题——组合总和 II 的思路。

所以要特别注意这两道题的区别。

7. 为什么最后要删除最后一个元素？

combination.remove(combination.size() - 1);

这是回溯的“撤销选择”步骤。

流程是这样的：

1. 先把当前数字加入路径

2. 递归往下搜索

3. 搜索完成后，把这个数字删掉

4. 再尝试下一个数字

这样才能保证每次递归结束后，路径恢复到进入这一层之前的状态。

这就是回溯这个名字的由来： 走完一条路，再退回来，继续试别的路。

手动模拟一遍

我们用最经典的例子来走一遍：

candidates = [2,3,6,7], target = 7

初始调用

backtrack([2,3,6,7], 7, 0, [])

当前路径为空，还需要凑出 7。

第一层：选择 2

路径变成：

[2]

剩余目标值：

5

递归进入：

backtrack(..., 5, 0, [2])

注意这里 start 仍然是 0，因为 2 可以重复选。

第二层：再选 2

路径变成：

[2,2]

剩余目标值：

3

继续递归。

第三层：再选 2

路径：

[2,2,2]

剩余目标值：

1

这时候继续往后看，发现最小候选数 2 已经大于 1，直接剪枝返回。

于是回退，尝试下一种选择。

第三层：改选 3

路径：

[2,2,3]

剩余目标值：

0

说明找到一组合法答案，加入结果集。

回到第一层：改选 7

路径：

[7]

剩余目标值：

0

又找到一组答案。

最终结果就是：

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

为什么不会出现重复组合？

因为整个搜索过程中，我们始终规定：

• 当前层从 start 开始选

• 后面的递归也只能从当前元素及其后面继续选

这就保证了组合中的元素顺序始终非递减。

例如：

• [2,2,3] 会被生成

• 但 [2,3,2] 不会被生成

• [3,2,2] 也不会被生成

所以虽然我们没有显式去重，但通过控制搜索顺序，已经天然避免了重复。

这也是很多组合类回溯题的核心技巧。

复杂度分析

这道题的时间复杂度不太适合用一个简单的公式精确表示，因为它本质上是在搜索一棵回溯树。 不同输入下，搜索空间差异会比较大。

一般可以这样理解：

• 最坏情况下，需要尝试大量组合

• 所以时间复杂度是指数级的

通常写作：

O(2^target)

或者更宽泛地说：

时间复杂度取决于解空间大小和回溯树规模。

空间复杂度

递归调用栈的深度，最坏情况下取决于目标值和最小数字。 所以额外空间主要来自：

• 递归栈

• 当前路径 combination

一般可以理解为：

O(target)

当然，如果把结果集本身也算进去，最终空间还要更大。

这道题真正想考什么？

这道题表面上是在求“和为 target 的组合”，但本质上考察的是几个回溯中的核心点。

第一，路径和状态的定义

你必须清楚：

• 当前路径是什么

• 当前剩余目标值是什么

• 这一层从哪个位置开始选

如果这些状态定义不清楚，代码很容易写乱。

第二，如何避免重复

这道题没有用 Set 去重，而是通过控制 start 实现天然去重。

这是一种非常常见、也非常重要的技巧。

第三，如何做剪枝

排序后，当 candidates[i] > target 时直接停止，这能省掉很多无意义递归。

所以这道题不是单纯的“暴力搜索”，而是：

有顺序控制的回溯 + 有效剪枝。

和“组合总和 II”有什么区别？

这道题和后面的“组合总和 II”特别容易混。

组合总和（本题）

• 一个数字可以重复使用

• 所以下一层递归传的是 i

组合总和 II

• 每个数字只能用一次

• 所以下一层递归传的是 i + 1

• 而且通常数组里可能有重复元素，还要额外处理去重

所以这两题表面很像，但递归参数的写法并不一样。

总结

这道题的核心思想可以概括成一句话：

通过回溯不断尝试选择候选数字，在保证组合有序的前提下搜索所有和为 target 的路径，并借助排序进行剪枝。

具体步骤就是：

1. 先对数组排序

2. 用回溯函数维护当前路径和剩余目标值

3. 当剩余目标值为 0 时，记录答案

4. 从 start 开始枚举候选数，避免重复组合

5. 由于数字可以重复使用，递归时继续传当前下标 i

6. 如果当前数字已经大于剩余目标值，直接剪枝停止

这是一道非常典型、也非常值得反复理解的回溯题。 因为它几乎把回溯里的几个核心点都串起来了：

• 路径记录

• 递归搜索

• 撤销选择

• 顺序控制

• 剪枝优化

把这道题真正吃透之后，再去看：

• 组合总和 II

• 子集

• 全排列

• 分割回文串

这些题时，你会更容易理解“回溯到底是在做什么”。

因为“组合总和”本身就是一道非常经典的回溯模板题。