手帐 Blog

主题

19 · 递归心智与回溯框架 ​

目标：口述「做选择 → 递归 → 撤销」三步；默写子集模板；理解组合与子集的区别。

为什么面试会考 ​

回溯 = 带撤销的 DFS。面试常考子集、排列、组合总和，看你能不能：

  1. 把「枚举所有可能」拆成树形决策；
  2. 写出统一模板（做选择 / 递归 / 撤销）；
  3. 处理去重、剪枝、边界。

前端岗不一定天天写回溯，但中等题能区分「会背题」和「真会想」。

零基础概念：递归三问 ​

写任何递归前，先答三问：

问题子集（78）怎么答
终止条件？当前下标 start 扫完数组，或每层都可选「收工」
单层做什么？从 start 起，依次把 nums[i] 加入路径
返回值？本题收集所有路径，通常 void，结果放外部 res

回溯比纯递归多一步：撤销选择（恢复现场），才能试下一条分支。

零基础概念：决策树直觉 ​

以 nums = [1, 2, 3] 子集为例，每个位置「选 / 不选」或「从某下标起选下一个」都会长成一棵树：

text
[]
├─ [1]
│  ├─ [1,2]
│  │  ├─ [1,2,3]
│  │  └─ [1,2]
│  └─ [1,3]
│     └─ ...
└─ [2]
   └─ ...

子集：顺序无关，用 start 保证只往后选，避免 [2,1] 重复。
组合：从 n 个数里选 k 个，与子集类似，但到 k 就停。

JS 模板 / 套路：回溯通用框架 ​

javascript
/**
 * @param {number[]} nums
 * @return {void} 结果写入 res
 */
function backtrack(nums, start, path, res) {
  // 1. 收集结果（有的题在这里收，有的在终止条件收）
  res.push([...path]);

  // 2. 遍历选择列表
  for (let i = start; i < nums.length; i++) {
    // 做选择
    path.push(nums[i]);
    // 递归：下一层只能从 i+1 选（子集/组合）
    backtrack(nums, i + 1, path, res);
    // 撤销选择
    path.pop();
  }
}

口诀：选 → 往下钻 → 撤回 → 试下一个。

与 DFS 的区别：DFS 往往「走过就不回头」；回溯会 pop 恢复，同一层要试完所有分支。

精讲：LeetCode 78. 子集（完整） ​

题意：无重复元素，返回所有子集（幂集）。

思路：

  • 每个元素选或不选等价于：进入递归时先「收当前 path」，再从 start 往后逐个尝试加入。
  • 用 start 而不是 0，保证 [1,2] 与 [2,1] 不重复。
javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  const res = [];
  const path = [];

  function dfs(start) {
    res.push([...path]); // 每个节点都是合法子集

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
};
  • 时间：O(n · 2^n)（约 2^n 个子集，每个拷贝 O(n)）。
  • 空间：递归栈 O(n)，不计结果数组。

边界：nums 为空 → [[]]；单元素 → [[], [x]]。

精讲入门：LeetCode 77. 组合（与子集对比） ​

题意：1..n 中选 k 个，返回所有组合。

与子集模板的唯一差别：路径长度到 k 才收集，且不必每层都 push 进答案。

javascript
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const res = [];
  const path = [];

  function dfs(start) {
    if (path.length === k) {
      res.push([...path]);
      return;
    }
    // 剪枝：还剩 need 个，从 start 到 n 必须够选
    const need = k - path.length;
    for (let i = start; i <= n - need + 1; i++) {
      path.push(i);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(1);
  return res;
};
对比子集 78组合 77
何时收集每层都收集仅 path.length === k
枚举起点01（题意是 1..n）
剪枝可选建议写（面试加分）

练习清单（先提示，自己写） ​

题号一句话提示
LeetCode 78. 子集默写本篇框架；每层 res.push 再 for
LeetCode 77. 组合到 k 才收；i <= n - need + 1 剪枝
LeetCode 216. 组合总和 III77 + 和为 n 的剪枝（预习第 20 篇）
LeetCode 90. 子集 II排序后 i > start && nums[i]===nums[i-1] 跳过

今日验收 checklist ​

  • [ ] 能口述「做选择 / 递归 / 撤销」三步，并画 [1,2,3] 子集树
  • [ ] 不看稿写出 78 子集完整 JS 并 AC
  • [ ] 说清子集与组合：何时 res.push、为何用 start
  • [ ] 77 组合能写出剪枝条件 i <= n - need + 1

若你以前见过 ​

蓝桥里「DFS 搜方案」和回溯是一家人：C++ 里 vector 回溯要 push_back + pop_back，JS 用 path.push + path.pop。注意 res.push([...path]) 要拷贝，不能直接 res.push(path)，否则后面 pop 会改到已收集的答案。