Combination Sum（组合总和）

题目 / Problem

中文： 给定一个由互不相同的整数构成的数组 candidates 和一个目标整数 target，返回所有元素之和等于 target 的唯一组合。答案可以按任意顺序返回。

candidates 中的同一个数字可以选择无限次。如果两个组合中至少有一个数字的使用次数不同，就认为它们是不同组合。

测试数据保证有效组合数量少于 150。

English: Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates whose chosen values sum to target. The combinations may be returned in any order.

The same candidate may be selected an unlimited number of times. Two combinations are unique if the frequency of at least one chosen number differs.

示例 / Examples

Example 1

Input:  candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

2 + 2 + 3 = 7
7 = 7

数字 2 可以重复选择，因此 [2,2,3] 合法。以上是仅有的两个唯一组合。
Candidate 2 may be reused, so [2,2,3] is valid. These are the only two unique combinations.

Example 2

Input:  candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3

Input:  candidates = [2], target = 1
Output: []

最小候选数 2 已经大于目标值 1，因此不存在有效组合。
The smallest candidate 2 already exceeds target 1, so no valid combination exists.

约束 / Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 中所有元素互不相同。
All elements of candidates are distinct.
1 <= target <= 40

解题思路：回溯 / Approach: Backtracking

回溯法逐步构造当前组合 path，并记录仍需凑出的金额 remaining：
Backtracking builds a current combination path while tracking the remaining sum remaining:

如果 remaining === 0，当前组合正好满足目标，将它的副本加入结果。
If remaining === 0, the current combination reaches the target, so append a copy to the result.
如果某个候选值大于 remaining，继续选择只会超出目标，应停止该分支。
If a candidate exceeds remaining, choosing it would overshoot the target, so stop that branch.
选择一个候选值后递归探索，返回时撤销该选择，继续尝试其他值。
After choosing a candidate, recurse; when the call returns, undo the choice and try other values.

这正是“选择 → 递归 → 撤销选择”的回溯模板：
This is the standard “choose → recurse → undo” backtracking pattern:

path.push(candidate);      // 选择 / Choose
backtrack(...);            // 递归 / Recurse
path.pop();                // 撤销 / Undo

如何避免重复组合？ / How Are Duplicate Combinations Avoided?

组合不关心元素顺序，因此 [2,2,3]、[2,3,2] 和 [3,2,2] 应视为同一个答案。
Combination order does not matter, so [2,2,3], [2,3,2], and [3,2,2] represent the same answer.

为避免生成这些不同排列，递归函数使用参数 start：
To avoid generating these permutations, the recursive function uses a start parameter:

当前层只能从下标 start 开始向后选择。
The current recursion level may choose only indices from start onward.
选中下标 i 后，下一层仍从 i 开始，因为同一个数字可以重复使用。
After choosing index i, recurse with i again because the same candidate may be reused.
不会回头选择更小下标的数字，所以每个组合始终按非递减顺序生成。
Earlier indices are never revisited, so every combination is generated in nondecreasing order.

正确 / Correct: backtrack(i, remaining - candidate)

如果每个数只能用一次才使用 / Use only when each value is single-use:
backtrack(i + 1, remaining - candidate)

排序与剪枝 / Sorting and Pruning

先对候选数组排序。当 candidate > remaining 时，后面的候选值只会更大，因此可以直接 break，而不只是 continue。
Sort the candidates first. When candidate > remaining, every later value is at least as large, so use break rather than merely continue.

排序不是去重所必需的，因为题目保证候选值互不相同；它主要用于有序生成组合和提前剪枝。
Sorting is not required to deduplicate candidates because they are already distinct; it mainly enables ordered generation and early pruning.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSum(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b);
  const result = [];
  const path = [];

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }

    for (let i = start; i < sorted.length; i++) {
      const candidate = sorted[i];

      if (candidate > remaining) {
        break;
      }

      path.push(candidate);
      backtrack(i, remaining - candidate);
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}

这里复制并排序候选数组，避免 sort() 修改传入的 candidates。
The candidates are copied before sorting so sort() does not modify the input array.

找到答案时必须使用 [...path] 保存副本。如果直接保存 path，所有结果会引用同一个后续仍在变化的数组。
Append [...path] when a solution is found. Pushing path directly would make every result reference the same array that continues to change.

执行过程 / Walkthrough

以 candidates = [2,3,6,7]、target = 7 为例：
For candidates = [2,3,6,7] and target = 7:

[]，remaining = 7
├─ [2]，remaining = 5
│  ├─ [2,2]，remaining = 3
│  │  ├─ [2,2,2]，remaining = 1 → 2 > 1，剪枝 / Prune
│  │  └─ [2,2,3]，remaining = 0 → 记录 / Record
│  └─ [2,3]，remaining = 2 → 3 > 2，剪枝 / Prune
├─ [3]，remaining = 4
│  └─ [3,3]，remaining = 1 → 3 > 1，剪枝 / Prune
├─ [6]，remaining = 1 → 6 > 1，剪枝 / Prune
└─ [7]，remaining = 0 → 记录 / Record

最终得到：
Final result:

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

`start` 参数的变化 / How `start` Changes

以寻找 [2,2,3] 为例：
For combination [2,2,3]:

当前路径 / Path	选择下标 / Chosen Index	下一层 `start`	原因 / Reason
`[]`	0（值 2）	0	允许再次选择 2 / May reuse 2
`[2]`	0（值 2）	0	允许再次选择 2 / May reuse 2
`[2,2]`	1（值 3）	1	可继续选择 3 或更大值 / May choose 3 or later values

进入下标 1 后不会再回到下标 0，所以不会生成 [2,3,2]。
After moving to index 1, recursion never returns to index 0, so [2,3,2] is never generated.

复杂度 / Complexity

回溯算法的运行时间与搜索树大小以及输出组合数量有关。设最小候选值为 m，递归最大深度不超过 target / m。
Backtracking time depends on the search-tree size and number of output combinations. If m is the smallest candidate, recursion depth is at most target / m.

时间复杂度：最坏为指数级，常写作 O(n^(target / m)) 的宽松上界；剪枝和 start 会显著减少实际搜索。
Time: Exponential in the worst case, with a loose bound of O(n^(target / m)); pruning and start substantially reduce practical work.
辅助空间复杂度：O(target / m)，用于递归调用栈和当前路径，不计算返回结果。
Auxiliary space: O(target / m) for the recursion stack and current path, excluding the output.
返回结果空间取决于有效组合数量及各组合长度。
Output space depends on the number and lengths of valid combinations.

为什么不能使用简单贪心？ / Why Does Simple Greedy Fail?

每次选择最大或最小候选值都不能保证找到所有组合，也不能保证找到解。例如 candidates = [2,3,5]、target = 8 有三个答案，单一路径的贪心选择无法枚举全部结果。
Always choosing the largest or smallest candidate cannot find every combination and may miss solutions. For candidates = [2,3,5] and target = 8, there are three answers, which no single greedy path can enumerate.

本题要求返回所有唯一组合，因此需要系统地搜索不同选择分支。
Because every unique combination is required, different choice branches must be explored systematically.

易错点 / Common Pitfalls

同一个候选数字可以无限次使用，因此递归时传入 i，不是 i + 1。
A candidate may be reused indefinitely, so recurse with i, not i + 1.
使用 start 限制后续选择，防止生成排列不同但内容相同的重复组合。
Use start to prevent duplicate combinations with different orderings.
找到组合时必须保存 path 的副本。
Save a copy of path when a combination is found.
递归返回后必须执行 path.pop() 撤销选择。
Call path.pop() after recursion to undo the choice.
排序后遇到 candidate > remaining 可以直接 break。
After sorting, use break when candidate > remaining.
题目要求组合唯一，不要求组合或结果数组使用特定顺序。
Combinations must be unique, but no specific ordering is required.

Combination Sum