讲解

回溯是「带着撤销的深度优先搜索」：沿一条选择路径走到底，走不通或走完了就退回上一步，换个选择继续——撤销（恢复现场）是它区别于普通 DFS 的标志。代码骨架高度统一：维护一个 path（当前选择序列），递归函数每层遍历本层所有可选元素，做选择、递归、撤销选择。「做选择 → 递归 → 撤销」三段式写熟，回溯题就拿到了框架分。

三类经典问题对应三种遍历方式。全排列：每层从「还没用过的元素」里选，需要 used 数组标记，终止条件是 path 长度等于 n——决策树有 n! 条路径，时间复杂度 O(n·n!)，这是本质复杂度，不存在多项式算法。子集：每个元素都有「选 / 不选」两态，用 start 参数控制「只能往后选」避免 [1,2] 和 [2,1] 重复；它的巧妙写法是每进入一个递归节点就把当前 path 收进结果——每个节点都是一个子集。组合（如组合总和）：同样用 start 防重，但允许元素复用时递归传 i 而不是 i+1；配合排序后剪枝（和已超 target 就 break）能砍掉大量分支。

剪枝是回溯从「能跑」到「跑得快」的关键：在进入递归前预判「这条路不可能出答案」，直接跳过。N 皇后是剪枝的天然教材：逐行放皇后，每列、两条对角线各用一个集合记录占用，放之前三查集合，冲突即跳过——n=8 时 92 种解、n=4 时 2 种解，没有剪枝的暴力根本跑不动稍大的 n。

示例

全排列、子集、组合总和、N 皇后计数四连发——同一个骨架，四种参数：

import assert from 'node:assert/strict';

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  function dfs() {
    if (path.length === nums.length) {
      result.push(path.slice()); // 必须拷贝，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 result;
}

function subsets(nums) {
  const result = [];
  const path = [];
  function dfs(start) {
    result.push(path.slice()); // 每个节点都是一个子集
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1); // 只能往后选，天然去重
      path.pop();
    }
  }
  dfs(0);
  return result;
}

function combinationSum(candidates, target) {
  const result = [];
  const path = [];
  let sum = 0;
  function dfs(start) {
    if (sum === target) {
      result.push(path.slice());
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (sum + candidates[i] > target) continue; // 剪枝
      sum += candidates[i];
      path.push(candidates[i]);
      dfs(i); // 元素可复用：传 i 而不是 i + 1
      sum -= candidates[i];
      path.pop();
    }
  }
  dfs(0);
  return result;
}

function totalNQueens(n) {
  let count = 0;
  const cols = new Set();
  const diag1 = new Set(); // row - col 恒定
  const diag2 = new Set(); // row + col 恒定
  function dfs(row) {
    if (row === n) {
      count++;
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);
      dfs(row + 1);
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }
  dfs(0);
  return count;
}

assert.strictEqual(permute([1, 2, 3]).length, 6);
assert.deepStrictEqual(permute([1]), [[1]]);
assert.strictEqual(subsets([1, 2, 3]).length, 8); // 2^3
assert.deepStrictEqual(combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]);
assert.strictEqual(totalNQueens(4), 2);
assert.strictEqual(totalNQueens(1), 1);

console.log('回溯示例全部通过');

横向对比四个 dfs 的参数差异：排列无 start 但要 used；子集有 start 且 i+1；可复用组合有 start 且传 i；N 皇后每层固定选「第 row 行的列号」。参数差异就是问题差异，框架本身纹丝不动。

常见坑

  • 结果里存的是 path 的引用：回溯会反复修改同一个 path，收结果必须 slice() 拷贝——最常见的 bug，症状是结果数组里全是空数组或同一个数组。
  • 撤销不完整：做选择和撤销必须严格对称（push 对 pop、add 对 delete、置 true 对置 false），漏一处状态就被污染，且 bug 隐蔽。
  • 去重靠事后过滤：组合类问题该用 start 参数在生成时防重，生成完再 Set 去重既慢又丑。
  • 该剪枝时硬跑：如组合总和中 sum 已超 target 还继续递归，复杂度直接失控；排序后 break 剪枝效果更好。
  • 误把回溯当多项式算法：排列、子集的本质复杂度是阶乘/指数级，n 稍大就跑不动是题目性质，不是你的代码错了。

小结

回溯 = 做选择 → 递归 → 撤销的 DFS；排列用 used、子集/组合用 start 防重、可复用传 i、剪枝保性能；结果收 path 的拷贝。下一章看搜索的另一翼：广度优先搜索。