30 秒速记

• 递归回溯不是玄学，它就是「做选择 → 往下走 → 撤销选择」的穷举套路
• 门槛主要在心理上：一看到「思想」两个字就先吓住了
• 学法：从最小的例子手推，比如两个数的全排列，看每一层做了什么
• 先能写出能跑的小例子，再回头补术语和定义
• 一道题会了不算，换一道同类题还能写出来才算

递归回溯听起来唬人，其实就是一套能反复套用的穷举套路，难的是第一次跨过心理门槛。 很多人一看到「思想」就觉得是一大坨理论，还没开始看题就先放弃了。我的建议是别从定义入手，拿一个最小的例子手推一遍，比如 [1,2] 的全排列，每一层选了谁、什么时候返回、返回后数组变成什么样，在纸上画出来。画清楚一次，后面的组合、子集都是换汤不换药。

30 秒速记

• 面试不考背定义，考能不能把题做出来 → 以题为纲
• 先手画搜索树的前两层：每层有哪些候选、哪些分支该剪
• 模板里的参数各管一件事：path 记当前选择，start 管不回头，used 管不重复，remain 管剩余目标
• 用最小输入逐步跟踪，再拿空输入、重复元素、无解验证边界
• 「思想」本质是套路，吃透一个能带走一大批题

这一节别纠结什么是递归、什么是回溯，直接做题，从题里认识套路。 面试里算法几乎不考背概念，看的是你能不能把题写出来。我的做法是遇到「列出所有方案」的题，先在纸上画出搜索树的前两层，看每一层在做什么重复的选择、什么时候停。画出来之后，代码里的 path、start、used 分别对应什么就很清楚了。刚开始想不到递归很正常，做完全排列、子集、组合这三道，自然会形成条件反射。

30 秒速记

• 全排列 = 逐个填坑：第 depth 层决定第 depth 个位置放谁
• path 记当前排列，used[i] 记下标 i 在这条路径上用没用过
• 每轮固定三步：选择 → 递归 → 撤销，撤销必须和选择对称
• 收集答案写 [...path]，直接存 path 所有结果会变成同一个数组
• n 个不同元素共 n! 种，光输出就要 O(n·n!)

全排列可以看成填坑：有几个数就有几个坑，每一层从还没用过的数里挑一个填进去，填满了就是一个答案。 用 path 存当前填好的部分，用 used 记哪些数已经用过，避免同一个数出现两次。递归返回后要把刚才的选择撤销掉，path.pop() 加上 used[i] = false，这样兄弟分支才能从干净的状态开始。最常见的坑是收集结果时直接 res.push(path)，因为后面还会继续改这个数组，最后所有结果都一样。

function permute(nums) {
  const res = [], path = [], used = []
  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 // permute([1,2,3]) 共 6 个
}