手帐 Blog

主题

20 · 回溯经典 ​

目标：默写全排列与组合总和模板；说清「用过的数」与「可重复选」差在哪。

为什么面试会考 ​

46 / 39 是回溯八股：

  • 排列：顺序不同算不同；用 used 数组
  • 组合总和：可重复选同一数字；递归时下标不 +1 或仍从 i 开始

框架同 19，变的是「下一层从哪开始 / 能不能再用」。

零基础概念 ​

题型下一层起点是否用 used
子集 / 组合i + 1通常不用
排列0 重新扫要 used
组合总和（可重复）仍从 i不用

剪枝：排序后，若 remain - candidates[i] < 0 可直接 break。

JS 模板：排列 ​

js
function permute(nums) {
  const res = []
  const path = []
  const used = Array(nums.length).fill(false)
  const dfs = () => {
    if (path.length === nums.length) {
      res.push([...path])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true
      path.push(nums[i])
      dfs()
      path.pop()
      used[i] = false
    }
  }
  dfs()
  return res
}

精讲题 ​

LeetCode 46. 全排列 ​

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const res = []
  const path = []
  const used = Array(nums.length).fill(false)
  const dfs = () => {
    if (path.length === nums.length) {
      res.push(path.slice())
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true
      path.push(nums[i])
      dfs()
      path.pop()
      used[i] = false
    }
  }
  dfs()
  return res
}

LeetCode 39. 组合总和 ​

候选可重复使用；结果去重靠「从下标 i 继续」而不是从 0。

js
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  candidates.sort((a, b) => a - b)
  const res = []
  const path = []
  const dfs = (start, remain) => {
    if (remain === 0) {
      res.push(path.slice())
      return
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remain) break
      path.push(candidates[i])
      dfs(i, remain - candidates[i]) // 仍从 i：可重复
      path.pop()
    }
  }
  dfs(0, target)
  return res
}

对照：LeetCode 40. 组合总和 II（练习前先看区别） ​

每个数字最多用一次 → dfs(i + 1, ...)；同层去重：i > start && candidates[i] === candidates[i-1] 则 skip。

练习清单 ​

题提示
LeetCode 47. 全排列 II排序 + 同层去重
LeetCode 77. 组合n 选 k，start 向后
LeetCode 216. 组合总和 III1～9 选 k 个和为 n
LeetCode 22. 括号生成左右括号计数剪枝

今日验收 ​

  • [ ] 46 能默写 used + 撤销
  • [ ] 39 能解释为何 dfs(i, ...) 不是 i+1
  • [ ] 能对比 39 与 40 的差异一句话

若你以前见过 ​

排列 / 组合的「是否看重顺序」就是高中排列组合；代码里用 used 与 start 落地。