遍历视角：回溯与 DFS

回溯算法框架

你已经写过一遍了

两种思维那篇里，用遍历视角求最大深度时写过这么一段：

depth++;              // 进入这个节点
traverse(node.left);
traverse(node.right);
depth--;              // 离开这个节点

「进入时做选择、离开时撤销」——这就是回溯的全部内容。 这一篇要做的只是给它一个框架、一个名字，然后套到具体题型上。

框架

const res = [];

function backtrack(路径, 选择列表) {
  if (满足结束条件) {
    res.push([...路径]);
    return;
  }

  for (const 选择 of 选择列表) {
    做选择;
    backtrack(路径, 选择列表);
    撤销选择;
  }
}

⭐ 需要你动脑的只有三处：结束条件是什么、选择列表怎么来、做/撤销一次选择具体是什么操作。 for 循环加中间那三行的骨架，一个字都不用改。

🚨 res.push([...路径]) 里的展开必须有

这是回溯最高频的错误，而且症状极具迷惑性。

路径 在整个递归过程中只有一个数组实例——所有分支共用它。 如果写成 res.push(路径)，存进 res 的是同一个引用； 等递归全部结束、所有选择都被撤销之后，那个数组会被 pop 空。

⚠️ 结果是 res 里躺着 N 个空数组，长度还是对的。实测 permute([1,2,3])：

忘了展开     [ [], [], [], [], [], [] ]     6 项 ✅ 长度对
正确                                        6 项

n=1/3/4 分别得到 1/6/24 项，个数一个不差；子集版（res.push(track)）同样是 8 项全空。一眼看去像是「递归没执行」或者「结束条件写错了」， 实际上递归完全正确，错的只是没拷贝。

⭐ 有个一秒钟确诊的办法：它们根本不是 N 个空数组， 是同一个数组对象的 N 个引用。

> res.every(x => x === res[0])
true                                          ← 六项是同一个对象

> res[0].push('X'); res
[['X'],['X'],['X'],['X'],['X'],['X']]         ← 改一项，六项一起变

👉 在调试器里改 res[0] 一眼就看出来。而「递归没执行」不会有这个现象。

全排列：用 used 数组

function permute(nums) {
  const res = [], track = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (track.length === nums.length) {
      res.push([...track]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;          // 这个数已经在路径里了

      track.push(nums[i]);            // 做选择
      used[i] = true;

      backtrack();

      track.pop();                    // 撤销选择
      used[i] = false;
    }
  }

  backtrack();
  return res;
}

⚠️ 撤销必须与做选择严格对称：push 配 pop，used[i] = true 配 used[i] = false。

只撤一半的症状不是「数量变少」，是恒为 1 条，与 n 无关：

n              1    2    3    4     5     6
正确           1    2    6   24   120   720
忘 used[i]=false   1    1    1    1     1     1
忘 track.pop()     1    1    1    1     1     1

🚨 而且那唯一一条恰好是原顺序 [1,2,3,…] —— 看起来特别像「递归只走了第一条路」。 n=6 时 720 条塌成 1 条，不是「骤减」那么温和。

⭐ 两种撤法漏一半，结果一模一样，内部却完全相反。数一下递归调用次数就分得开：

n = 7          递归调用次数    结果条数   track 最终长度
正确                 13700       5040          0
忘 used[i]=false         8          1          7      ← 递归树塌了
忘 track.pop()       13700          1      13699      ← 递归树没变，是 track 炸了
  • 忘 used[i] = false —— 第一条路走完，所有 used 都是 true， 后面的分支全被 continue 掉。递归树从 13700 个节点塌成 8 个。
  • 忘 track.pop() —— 递归树一个节点都没少，13700 次调用照跑。 但 track 只进不出，长度直接等于走过的节点数（13699）， track.length === nums.length 这个结束条件越过一次之后再也命中不了。

📌 判据：结果只剩 1 条时，先看递归调用了多少次。 塌到个位数是漏了状态复原，次数没变就是漏了路径复原。

子集与组合：用 start 参数

function subsets(nums) {
  const res = [], track = [];

  function backtrack(start) {
    res.push([...track]);             // 每个节点都是一个答案

    for (let i = start; i < nums.length; i++) {
      track.push(nums[i]);
      backtrack(i + 1);               // 下一层从 i+1 开始，不回头
      track.pop();
    }
  }

  backtrack(0);
  return res;
}

组合就是子集加一个长度限制——把 res.push 挪进 if (track.length === k) 即可。

两类题型的差别只在两处

排列 组合 / 子集
控制重复 used 数组 start 参数
循环起点 每层都从 0 开始 从 start 开始
收集答案 只在叶子节点 每个节点都收（子集）

⭐ 本质差别是顺序算不算数。 排列里 [1,2] 和 [2,1] 是两个答案，所以每层都要把所有数过一遍， 靠 used 排除已经用过的；组合里它们是同一个，所以用 start 强制「只能往后挑」， 从根上就不产生逆序的分支。

📌 记住这一条，就不会纠结「这题该用 used 还是 start」—— 先问自己「换个顺序算不算新答案」。

去重：先排序，再跳过同层相邻的重复

输入里有重复元素时（比如 [1,2,2] 求子集），上面的模板会产出重复答案。

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);         // 🚨 前提：必须先排序
  const res = [], track = [];

  function backtrack(start) {
    res.push([...track]);
    for (let i = start; i < nums.length; i++) {
      // 同一层里，跳过与前一个相同的值
      if (i > start && nums[i] === nums[i - 1]) continue;

      track.push(nums[i]);
      backtrack(i + 1);
      track.pop();
    }
  }

  backtrack(0);
  return res;
}

🚨 条件是 i > start，不是 i > 0。差一个字，结果差很多：

  • i > start —— 只在同一层内跳过重复。同一个值可以出现在路径的不同层上， 所以 [2,2] 这种答案保得住。
  • i > 0 —— 不分层地跳过所有与前一个相同的值。 凡是包含重复元素的子集，全部丢失。

拿 nums = [1,2,2] 实测：

i > start（正确）：[] [1] [2] [1,2] [2,2] [1,2,2]      6 个
i > 0  （错误）：  [] [1] [2] [1,2]                    4 个

⚠️ 丢的不是一个而是两个，而且丢的恰好是带重复元素的那些—— 也就是这道题真正要考的部分。剩下的答案全对，所以看起来像「少了几个边界情况」， 很容易往判重条件之外的地方去查。

⚠️ 丢的这两个是随机输入下的普遍规律，不是这一个例子的巧合： 2000 组随机输入里有 1362 组发生丢失、共丢掉 9369 个子集， 没有一个是无重复元素的 —— 丢的永远是这道题真正要考的那部分。

⚠️ 排序是前提，但「完全失效」只占三分之一

不排序的话相同的值不相邻，nums[i] === nums[i-1] 命中不了，去重会失效且不报错。 但失效的程度取决于输入长什么样：

输入        正确个数   不排序    全枚举 2ⁿ
[1,2,2]          6        6         8     ← 输入本来就有序，碰巧全对
[2,2,1]          6        6         8     ← 重复值恰好相邻，也全对
[2,1,2]          6        8         8     ← 完全失效，退化成全枚举
[1,2,1,2]        9       16        16     ← 完全失效

3000 组随机输入分三档：

完全失效（结果 = 2ⁿ）   1047 组 = 34.9%
部分失效（比正确多，但没到 2ⁿ）  904 组 = 30.1%
碰巧全对                 1049 组 = 35.0%

🚨 「碰巧全对」占了三分之一 —— 只要重复的值本来就挨在一起， 不排序也看不出问题。所以自测时必须专门喂一个相同值被隔开的输入 （[2,1,2] 就够），否则这个 bug 一路绿灯。

复杂度

回溯的复杂度看递归树的规模，通常是指数级的：

  • 全排列：O(n × n!) —— n! 个叶子，每个叶子拷贝一次长度为 n 的路径
  • 子集：O(n × 2ⁿ) —— 2ⁿ 个节点

数一遍实际拷贝了多少个元素，排列这条是精确相等而不只是同阶：

排列    n    叶子数     n!    递归节点数   拷贝元素总数     n·n!
        3         6      6           16           18       18   ✅ 相等
        5       120    120          326          600      600   ✅
        7      5040   5040        13700        35280    35280   ✅
        8     40320  40320       109601       322560   322560   ✅

子集    n    节点数    2ⁿ    拷贝元素总数    n·2ⁿ    实际/n·2ⁿ
        3         8      8             12       24       0.50
        5        32     32             80      160       0.50
       10      1024   1024           5120    10240       0.50
       14     16384  16384         114688   229376       0.50

⭐ 子集那边的常数是 1/2：拷贝总量恰好是 n·2ⁿ⁻¹。 因为 2ⁿ 个子集的平均长度是 n/2，不是 n —— 大部分子集比全集短得多。 数量级没错，但别以为每个节点都要拷 n 个元素。

⭐ 这不是写得不好，是问题本身的答案数量就这么多。 回溯题的优化空间在剪枝（提前判断这条分支不可能有答案就 return）， 不在降低这个数量级。

下一步

回溯的选择做在「树枝」上。把同样的操作挪到「节点」上，就是 DFS——一个位置之差，两种代码形态。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。