本文概览：本文以LeetCode题目"组合总和"为例，讲解回溯法在可重复选择、结果不计顺序场景下的应用，以及和子集问题的对比

一、题目

组合总和题目

二、题目分析

题目要求：给定一个无重复元素的正整数数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。同一个数字可以被无限制重复选取，但结果集不能包含重复的组合（[1,2] 和 [2,1] 算重复）

比如 candidates = [2, 3, 6, 7]，target = 7，输出：

1
[[2, 2, 3], [7]]
  • [2, 2, 3]：2 被选了两次，加起来 = 7
  • [7]：直接选一个 7

这题一开始容易想到"先排序，用前缀和"，但这里行不通：

  1. 前缀和的前提是结果必须是原数组的连续子数组，但本题的组合可以从任意位置选，甚至可以重复选
  2. 本题的组合可以重复选取同一个元素，前缀和只能每个元素用一次

所以本题的正确思路是回溯——遍历所有可能的选择路径

和子集问题的对比：

子集 组合总和
每个元素能选几次 最多 1 次 无限次
结果 所有子集 和 = target 的组合
终止条件 遍历完所有元素 sum == target 或 sum > target
递归参数 start（下次从 start+1 开始） start（下次从 start（含自己）开始）

核心区别：子集递归时传 i + 1（不能再选自己），组合总和递归时传 i（可以继续选自己）

思路概览

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
class Solution {
    private final List<List<Integer>> result = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int sum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return new ArrayList<>();
        }
        backtrack(candidates, target, 0);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            sum += candidates[i];
            backtrack(candidates, target, i);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

思路简要说明

  1. 两个终止条件：sum == target 时收集结果；sum > target 时剪枝返回
  2. start 参数：控制"只往后选"，避免 [2,3] 和 [3,2] 重复
  3. 递归传 i 不是 i+1：允许重复选择当前元素

三、思路详解

第一步：为什么不能用前缀和

看到"数组求和 = target"，很多人第一反应是排序 + 前缀和。但仔细看题目：

问题一：结果不是连续子数组

前缀和解决的是"从原数组中找一段连续的子数组"，但本题的组合可以从任意位置挑，比如 candidates = [2, 3, 6, 7] 中挑 [2, 2, 3]，2 用了两次，位置也不连续

问题二：可以重复选择

前缀和的每个元素只被计算一次，本题允许一个元素被选无数次，前缀和天然做不到

所以只能回溯——枚举所有可能的选择路径

第二步：为什么用 start 参数

如果不控制顺序，[2, 3] 和 [3, 2] 会被算成两个组合，题目视为重复。解决办法是规定只往后选——每次选完一个元素后，下次选择只能从当前位置开始往后

以 candidates = [2, 3, 6, 7]，target = 7 为例：

1
2
3
4
5
6
选 2（i=0）后，下次只能从 i=0 开始（含 2 自己），即 {2, 3, 6, 7}
  选 2（i=0）后，下次还是从 i=0 开始
    选 2 → sum=6，继续
    ...
  选 3（i=1）后，下次从 i=1 开始（含 3），即 {3, 6, 7}
    不能回头选 2，否则会出现 [2, 3, 2] 和 [2, 2, 3] 重复

这样保证每个组合的元素只按数组下标非递减顺序排列，天然去重

第三步：递归传 i 而不是 i+1

这是和子集问题最大的区别：

1
2
3
4
5
// 子集：每个元素最多选 1 次
backtrack(res, i + 1, nums, subset);

// 组合总和：可以重复选择
backtrack(candidates, target, i);

传 i 意味着"下次可以再选自己"，实现了元素的重复选择。以 candidates = [2, 3, 6, 7]，选到 2 之后：

1
2
3
4
5
6
第一次选 2 → path=[2]
  递归传 i=0，下次仍可以选 2
  第二次选 2 → path=[2, 2]
    递归传 i=0，下次仍可以选 2
    第三次选 2 → path=[2, 2, 2]，sum=6 < 7
      ...

第四步：两个终止条件

1
2
3
4
5
6
7
if (sum == target) {
    result.add(new ArrayList<>(path));
    return;
}
if (sum > target) {
    return;
}
  • sum == target：找到一个合法组合，收集后返回
  • sum > target：当前路径已经超出目标，继续往下加只会更大，直接剪枝返回

因为 candidates 都是正数，sum 只会越加越大，所以超过就没必要继续

第五步：回溯操作

for 循环内的四行代码是回溯的核心：

1
2
3
4
5
path.add(candidates[i]);        // 选：加入路径
sum += candidates[i];           // 选：更新总和
backtrack(candidates, target, i);  // 往下递归
sum -= candidates[i];           // 撤销：恢复总和
path.removeLast();              // 撤销：移除路径最后一个

选就是 add + sum+=，撤销就是 sum-= + removeLast。每次选完往深处走，回来后完整撤销，for 循环 i++ 换下一个元素

第六步：完整执行过程

以 candidates = [2, 3, 6, 7]，target = 7 为例：

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
backtrack(start=0, path=[], sum=0)
├── 选 2 → path=[2], sum=2
│   └── backtrack(start=0)
│       ├── 选 2 → path=[2,2], sum=4
│       │   └── backtrack(start=0)
│       │       ├── 选 2 → path=[2,2,2], sum=6
│       │       │   └── backtrack(start=0)
│       │       │       ├── 选 2 → sum=8 > 7，剪枝
│       │       │       ├── 选 3 → sum=9 > 7，剪枝
│       │       │       ├── 选 6 → sum=12 > 7，剪枝
│       │       │       └── 选 7 → sum=13 > 7，剪枝
│       │       ├── 选 3 → path=[2,2,3], sum=7  ✓ 收集 [2,2,3]
│       │       ├── 选 6 → sum=10 > 7，剪枝
│       │       └── 选 7 → sum=11 > 7，剪枝
│       ├── 选 3 → path=[2,3], sum=5
│       │   └── backtrack(start=1)
│       │       ├── 选 3 → sum=8 > 7，剪枝
│       │       ├── 选 6 → sum=11 > 7，剪枝
│       │       └── 选 7 → sum=12 > 7，剪枝
│       ├── 选 6 → sum=8 > 7，剪枝
│       └── 选 7 → sum=9 > 7，剪枝
├── 选 3 → path=[3], sum=3
│   └── backtrack(start=1)
│       ├── 选 3 → path=[3,3], sum=6
│       │   └── 后面都超，剪枝
│       ├── 选 6 → sum=9，剪枝
│       └── 选 7 → sum=10，剪枝
├── 选 6 → path=[6], sum=6
│   └── backtrack(start=2)
│       ├── 选 6 → sum=12，剪枝
│       └── 选 7 → sum=13，剪枝
└── 选 7 → path=[7], sum=7  ✓ 收集 [7]

最终结果：[[2, 2, 3], [7]]

第七步：和之前几道题的对比

全排列 子集（方法二） 电话号码 组合总和
顺序 关心 不关心 关心 不关心
元素能选几次 1 次 1 次（选/不选） 1 次（多选一） 无限次
参数 visited 数组 start（传 i+1） index start（传 i）
for 起点 每次从 0 开始 从 start 开始 从 0 开始（新映射串） 从 start 开始
收集时机 叶子节点 每次进入 叶子节点 sum == target

关键点：顺序关心 → 每次从 0 开始+visited；顺序不关心 → start 参数往后选。元素可复用 → 传 i；不可复用 → 传 i+1

复杂度分析

  • 时间复杂度：最坏 O(N^(target/min))，N 是候选数字个数，target/min 是最大递归深度（min 是最小的候选数）。实际有剪枝，运行速度更快
  • 空间复杂度：O(target/min)，递归深度最深的情况