回溯算法模板

面试回答： 回溯本质上是在一棵决策树上进行深度优先搜索。每一层枚举当前可选项，先做选择并进入下一层，递归返回后再撤销选择，使状态恢复到选择前。遇到不合法或不可能得到答案的分支时提前跳过，这就是剪枝。

核心模板

function solve(input) {
  const result = [];
  const path = [];

  function backtrack(/* 当前层需要的状态 */) {
    // 1. 收集答案
    if (满足结束条件) {
      result.push([...path]); // 保存快照，不能直接保存 path
      return;
    }

    // 2. 枚举当前层的所有选择
    for (const choice of 当前可选项) {
      // 3. 排除不合法或不可能成功的分支
      if (choice 不合法) continue;

      // 4. 做选择
      path.push(choice);
      更新状态(choice);

      // 5. 进入下一层决策
      backtrack(/* 更新后的状态 */);

      // 6. 撤销选择，恢复现场
      恢复状态(choice);
      path.pop();
    }
  }

  backtrack(/* 初始状态 */);
  return result;
}

最核心的三步是：

做选择();
backtrack();
撤销选择();

做题时先确定三个问题

  1. 路径是什么？ 已经做出的选择，例如当前排列或组合。
  2. 选择列表是什么？ 当前层还能选择哪些元素。
  3. 结束条件是什么？ 什么时候形成一个完整答案。

可以把执行过程理解为：

枚举选择 → 做选择 → 递归探索 → 撤销选择 → 尝试下一个选择

全排列示例

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      path.push(nums[i]);
      used[i] = true;

      backtrack();

      used[i] = false;
      path.pop();
    }
  }

  backtrack();
  return result;
}

used[i] 保证同一个元素在一条路径中只使用一次。递归返回后同时恢复 used[i] 和 path，其他分支才能从相同的初始状态继续搜索。

常见题型的状态设计

题型关键状态下一层如何推进
子集path、startIndex从 i + 1 继续选择
组合path、startIndex、剩余数量控制起点并按剩余数量剪枝
排列path、used每层遍历全部元素，跳过已使用项
棋盘搜索坐标、访问状态标记当前位置，搜索后撤销标记

去重、剪枝与常见错误

  • result.push(path) 保存的是同一个数组引用，后续回溯会改变它；应使用 result.push([...path]) 保存快照。
  • 组合问题通常用 startIndex，避免回头选择同一元素；排列问题通常用 used，因为每一层都可能选择任意未使用元素。
  • 输入含重复元素时，通常先排序，再跳过同一树层已经使用过的相同值；“同一树层去重”和“同一路径不可重复使用”不是一回事。
  • 剪枝必须保证被跳过的分支不可能产生合法答案，否则会漏解。
  • 做了哪些状态修改，递归返回后就要按相反方向完整恢复。

复杂度

回溯的复杂度取决于决策树规模。例如全排列需要生成 n! 个答案，每个答案复制路径需要 O(n)，因此时间复杂度为 O(n × n!)；递归栈和路径占用 O(n) 额外空间，不计返回结果。

一句话记忆：回溯就是在决策树上进行深度优先搜索，通过“选择、递归、撤销”枚举答案，通过剪枝减少无效搜索。