复盘 · LC 39 组合总和

题目

题号：LeetCode 39
名称：组合总和（Combination Sum）
难度：Medium
链接：leetcode.cn/problems/combination-sum/
今日代码：39-组合总和/index.js

题意

给定无重复正整数数组 candidates 和目标 target，找出所有和为 target 的组合。

同一数字可无限次使用。
组合不能重复：例如 [2,2,3] 与 [2,3,2] 算同一组合，只保留一种。
边界：target === 0 应收集当前空路径；无解返回 []。

涉及算法

标签	一句话
回溯 + start 索引	从 `i` 起选，下一轮仍从 `i` 起（允许重复选同一数）
剪枝	`tmpSum > target` 时立刻 return
组合 vs 排列	`dfs(i)` 而非 `dfs(i+1)` 且固定 start 顺序，避免 `[3,2,2]` 与 `[2,3,2]` 重复

教程对照：20 · 回溯经典（组合总和与全排列同框讲）。

评价我的解法

这是今天最接近标准模板的一题：tmpRes 累加和、tmpNumArr 记路径、dfs(index) 从当前下标继续（可重复选），大于 target 剪枝，等于 target 收集。思路对，性能也不错（76%）。

我的代码（摘自 39-组合总和/index.js，不含测例）：

javascript

var combinationSum = function (candidates, target) {
  const resArr = [];
  const len = candidates.length;
  const tmpNumArr = [];
  let tmpRes = 0;
  function dfs(index) {
    if (tmpRes === target) {
      resArr.push([...tmpNumArr]);
      return;
    }
    if (tmpRes > target) {
      return;
    }
    for (let i = index; i < len; i++) {
      const item = candidates[i];
      tmpRes += item;
      tmpNumArr.push(item);
      dfs(i);
      tmpNumArr.pop(item);
      tmpRes -= item;
    }
  }
  dfs(0);
  return resArr;
};

细节：

dfs(i) 而非 dfs(i+1)：正确，体现「可重复选取当前数」。
tmpNumArr.pop(item)：JS 的 pop 忽略参数，应写 tmpNumArr.pop()；现在能过是因为 LIFO 顺序刚好，属于写法坏习惯。
剪枝只判 >：等于 target 在循环外已处理；若先排序还可 tmpRes + candidates[i] > target break（本题数据量不大，可选优化）。
len 变量：可用可不用，不影响正确性。

小结：框架已是组合总和标准解；把 pop() 写对，再口述「为何传 i 不传 i+1」，面试就够用了。

最佳题解

排序 + 更强剪枝（可选）：

javascript

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

  function dfs(start, sum) {
    if (sum === target) {
      res.push([...path]);
      return;
    }
    if (sum > target) return;

    for (let i = start; i < candidates.length; i++) {
      const x = candidates[i];
      if (sum + x > target) break; // 排序后可 break
      path.push(x);
      dfs(i, sum + x);
      path.pop();
    }
  }

  dfs(0, 0);
  return res;
};

时间指数级（与解的数量相关），空间 O(target/min) 栈深量级。
与你版本核心一致；排序后 break 减少无效分支。

关联题目

题	为何相关
40. 组合总和 II	每个数只能用一次 + 去重
216. 组合总和 III	固定选 k 个数、和为 n
377. 组合总和 Ⅳ	求排列数，变 DP
78. 子集	同一 start 框架，无目标和

一句话带走

组合总和：和用变量带着走，选过的数还能再选所以递归传 i 不是 i+1，tmpSum > target 就剪枝返回。

复盘 · LC 39 组合总和 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​