39. 组合总和

题目描述

给定一个由不同正整数组成的数组 candidates 和一个正整数 target，找出所有和等于 target 的组合。

每个数字可以重复选择任意次，答案中不能包含重复组合。

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

解释：

2 + 2 + 3 = 7
7 = 7

[2, 2, 3] 和 [3, 2, 2] 只是顺序不同，属于同一个组合，不能重复加入答案。

为什么使用回溯？

我们需要不断尝试选择一个数字：

把数字加入当前组合。
递归寻找剩余目标值的组合。
递归返回后撤销这次选择，再尝试其他数字。

这就是回溯的“选择 → 递归 → 撤销选择”。

以 [2, 3, 6, 7]、目标值 7 为例，搜索过程的一部分是：

[]，剩余 7
├── 选择 2 → [2]，剩余 5
│   ├── 选择 2 → [2, 2]，剩余 3
│   │   ├── 选择 2 → [2, 2, 2]，剩余 1，无法继续
│   │   └── 选择 3 → [2, 2, 3]，剩余 0，找到答案
│   └── 选择 3 → [2, 3]，剩余 2，无法继续
├── 选择 3 → [3]，剩余 4
│   └── 选择 3 → [3, 3]，剩余 1，无法继续
├── 选择 6 → [6]，剩余 1，无法继续
└── 选择 7 → [7]，剩余 0，找到答案

回溯函数维护什么状态？

定义：

dfs(start, remaining)

start：本层可以从哪个候选数字开始选择。
remaining：距离目标值还差多少。
path：当前已经选择的数字。
result：保存所有合法组合。

例如：

path = [2, 2]
remaining = 3

表示当前和是 4，距离目标值 7 还差 3。

为什么需要 start？

组合不关心顺序。如果每层都从下标 0 开始选择，就会同时得到：

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

它们本质上是同一个组合。

使用 start 后，下一层只能选择当前数字或它后面的数字，路径中的数字下标不会倒退：

选择顺序可以是：2 → 2 → 3
不能再出现：    3 → 2

这样每个组合只会按照非递减顺序生成一次，不需要额外使用 Set 去重。

为什么递归传 i，而不是 i + 1？

选择 candidates[i] 后，递归调用：

dfs(i, remaining - candidates[i]);

仍然传入 i，表示下一层还可以继续选择当前数字。这正对应题目中的“同一个数字可以重复使用”。

例如选择一次 2 后，下一层仍从 2 开始，才能得到：

[2, 2, 3]

如果传入 i + 1，每个数字最多只能使用一次，那就变成了“组合总和 II”的规则。

终止条件

`remaining === 0`

当前路径中的数字之和正好等于 target，将路径加入结果：

result.push([...path]);

这里必须复制数组。path 后续还会继续 push 和 pop；如果直接保存 path，结果中的所有项都会指向同一个数组。

当前数字大于 remaining

候选数组排序后，如果：

candidates[i] > remaining

说明当前数字已经太大。后面的数字只会更大，也一定无法选择，因此可以直接 break，结束本层循环。

JavaScript 实现

var combinationSum = function (candidates, target) {
  // 复制后排序，既方便剪枝，也不会修改调用方传入的数组
  const sortedCandidates = [...candidates].sort((a, b) => a - b);

  const result = [];
  const path = [];

  // start：本层可以选择的最小候选下标
  // remaining：当前还需要凑出的数值
  const dfs = (start, remaining) => {
    // remaining 为 0，说明 path 中数字之和正好等于 target
    if (remaining === 0) {
      // 必须复制 path，因为 path 后续还会继续修改
      result.push([...path]);
      return;
    }

    // 只从 start 开始选择，保证组合中的候选下标不会倒退，
    // 从而避免 [2, 2, 3]、[2, 3, 2] 这样的重复排列。
    for (let i = start; i < sortedCandidates.length; i++) {
      const candidate = sortedCandidates[i];

      // 数组已经升序排列。
      // 当前数字超过 remaining，后面的数字也一定超过，可以直接结束。
      if (candidate > remaining) {
        break;
      }

      // 1. 选择当前数字
      path.push(candidate);

      // 2. 递归搜索。
      // 继续传 i 而不是 i + 1，表示当前数字可以重复使用。
      dfs(i, remaining - candidate);

      // 3. 撤销选择，恢复到进入本轮循环前的状态
      path.pop();
    }
  };

  dfs(0, target);
  return result;
};

代码推演

以寻找 [2, 2, 3] 的过程为例：

操作	`start`	`remaining`	`path`
初始调用	`0`	`7`	`[]`
选择 `2`	`0`	`5`	`[2]`
再选 `2`	`0`	`3`	`[2, 2]`
选择 `3`	`1`	`0`	`[2, 2, 3]`
保存答案	—	—	复制 `[2, 2, 3]`
撤销 `3`	—	`3`	`[2, 2]`
撤销第二个 `2`	—	`5`	`[2]`
撤销第一个 `2`	—	`7`	`[]`

递归调用中的 remaining 是传入下一层的新值；递归返回后，父层自己的 remaining 不会改变，只需要使用 path.pop() 恢复路径。

为什么排序？

排序不是为了去重。题目已经保证 candidates 中的数字互不相同。

排序的作用是让剪枝成立：

当前 candidate > remaining
→ 后续 candidate 更大
→ 后续都不可能加入组合
→ 可以直接 break

如果不排序，也可以得到正确答案，但遇到过大的候选时只能 continue，不能确定后面是否还有更小的数字。

正确性说明

在每次 dfs(start, remaining) 调用中，path 保存已经选择的数字，它们的和等于 target - remaining。

循环枚举从 start 开始的所有候选，因此不会遗漏合法的下一步选择。
递归继续传入 i，所以每个候选可以重复使用任意次。
下标不会倒退，所以每个组合只按非递减顺序生成一次，不会产生重复排列。
remaining === 0 时，路径之和恰好等于目标值，只有这种路径会加入答案。
排序剪枝只跳过大于 remaining 的数字，它们不可能出现在当前路径后面，因此不会漏掉合法答案。

所以算法能够且仅能够生成所有满足条件的不重复组合。

复杂度分析

回溯算法的运行时间取决于候选数字和目标值，不能简单写成只与候选数量有关的 O(2ⁿ)，因为每个数字可以重复选择。

设候选数量为 n，最小候选数为 m：

搜索深度最多为 target / m。
搜索树在最坏情况下呈指数增长，可以粗略表示为 O(n^(target / m))。
每找到一个答案，还需要复制当前路径，成本与该组合长度有关。
排序需要 O(n log n) 时间。
递归栈和路径最多占用 O(target / m) 空间，不包含返回结果。

实际运行通常会因为 remaining 递减、start 限制和排序剪枝而少于这个宽松上界。

与组合总和 II 的区别

题目	一个候选能否重复选择	递归传入的下标	是否需要同层去重
组合总和	可以	`i`	不需要，候选数字互不相同
组合总和 II	不可以	`i + 1`	需要，输入可能包含重复数字

记忆重点：

允许重复使用当前数字 → 递归传 i
不允许重复使用当前数字 → 递归传 i + 1

易错点

每层都从 0 开始枚举，产生相同组合的不同排列。
递归传入 i + 1，导致每个候选只能使用一次。
找到答案时直接保存 path，没有复制数组。
递归返回后忘记执行 path.pop()，导致路径状态污染其他分支。
未排序却使用 break 剪枝，可能错过后面更小的候选。
把本题复杂度机械写成 O(2ⁿ)，忽略候选可以无限重复、搜索深度受 target 影响。

面试时怎么说

使用回溯枚举组合。path 保存当前选择，remaining 表示还差多少，start 限制下一层只能选择当前下标及其后面的数字，从而避免不同顺序产生重复组合。选择候选 i 后递归仍传 i，表示它可以重复使用。候选数组先排序，当当前数字大于 remaining 时直接结束本层循环。remaining 为零时复制路径加入答案。

自测

为什么每一层不能都从下标 0 开始枚举？
为什么递归调用传入 i 而不是 i + 1？
为什么保存答案时必须复制 path？
为什么排序后可以使用 break 剪枝？

#39. 组合总和

#题目描述

#为什么使用回溯？

#回溯函数维护什么状态？

#为什么需要 start？

#为什么递归传 i，而不是 i + 1？

#终止条件

#remaining === 0

#当前数字大于 remaining

#JavaScript 实现

#代码推演

#为什么排序？

#正确性说明

#复杂度分析

#与组合总和 II 的区别

#易错点

#面试时怎么说

#自测