回溯算法

回溯是面试里最”直觉”的算法——你在高中列排列组合的时候就已经在用了，只是没人告诉你那叫回溯。

一句话理解

回溯 = 走一条路，走不通就退回来换一条。

在迷宫里你也是这么走的：往南走，撞墙了，退回来，往东走。回溯算法就是把这个过程形式化：系统地遍历所有可能，碰到死路就回退到上一个决策点。

核心模型：决策树

回溯的本质是遍历一棵决策树。树的每个节点代表”当前做了哪些选择”，每个分支代表”下一步可以做什么选择”，叶子节点就是完整解。

站在决策树的任意节点上，你只需要关心三件事：

要素	含义	例子（排列 [1,2,3]）
路径（Path）	已经做出的选择	[2]
选择列表（Choice List）	当前还能做什么选择	[1, 3]（2 已用过）
终止条件（Termination）	什么时候停下来	选择列表为空，路径长度 = n

回溯函数就是在这棵树上行走的一个指针。每到一个叶子节点，就把路径收集为解。

万能模板

不管什么回溯题，代码骨架都是这个：

function backtrack(path: number[], choices: number[]): void {
  // 触发终止条件
  if (terminationCondition) {
    result.push([...path]); // 收集当前路径为解
    return;
  }
  // 遍历当前所有选择
  for (const choice of choices) {
    if (!isValid(choice)) continue; // 剪枝：跳过不合法的选择
    // 做选择
    path.push(choice);
    // 递归进入下一层决策树
    backtrack(path, updatedChoices);
    // 撤销选择
    path.pop();
  }
}

记住这句话：在递归调用前做选择，在递归调用后撤销选择。

这就是回溯的全部秘密。前半句”做选择”是前序遍历位置，后半句”撤销选择”是后序遍历位置。两个操作对称，保证函数回到当前节点时状态和进入前完全一致。

为什么需要”撤销选择”？

因为你在用同一个 path 数组走整棵树。如果不撤销，走完左子树后 path 里残留了左子树的选择，走进右子树就错了。

        []
       /  \
    [1]    [2]
   /  \
[1,2] [1,3]

走 [1] → [1,2] 收集完解后，必须把 2 撤掉，path 回到 [1]，才能接着走 [1,3]。

经典题型

回溯题可以按”求什么”分三类：

题型	求什么	代表题目
排列（Permutation）	元素有序排列	[1,2,3] 的全排列
组合（Combination）	元素无序选取	C(4,2) 选 2 个
子集（Subset）	所有子集	[1,2] 的子集

加上约束类（N 皇后、数独、括号生成），一共四大类。

经典题一：全排列

LeetCode 46。给定不含重复数字的数组，返回所有全排列。

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const track: number[] = [];
  const used: boolean[] = new Array(nums.length).fill(false);
 
  function backtrack(): void {
    // 终止：路径长度 = 原数组长度
    if (track.length === nums.length) {
      result.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 result;
}

这里用 used 数组替代显式的选择列表——不在 track 里的元素就是可选的。

经典题二：括号生成

LeetCode 22 / HackerRank 13。生成 n 对括号的所有合法序列。

这题的决策树不是”选哪个元素”，而是”放 < 还是放 >”。所以选择列表是固定的两种，用两个计数器约束：

function generateBrackets(n: number): string[] {
  const result: string[] = [];
 
  function backtrack(open: number, close: number, cur: string): void {
    // 终止：两种括号配额都用完
    if (open === 0 && close === 0) {
      result.push(cur);
      return;
    }
    // 选择1：放 '<'，前提是还有配额
    if (open > 0) {
      backtrack(open - 1, close, cur + '<');
    }
    // 选择2：放 '>'，前提是有未闭合的 '<'
    if (close > open) {
      backtrack(open, close - 1, cur + '>');
    }
  }
 
  if (n === 0) return [''];
  backtrack(n, n, '');
  return result;
}

剪枝就在条件里：close > open 保证不会出现多余的 >。不需要事后过滤——回溯在生成时就只走合法路径。

经典题三：N 皇后

LeetCode 51。在 n×n 棋盘上放 n 个皇后，互不攻击。

每行放一个皇后，决策树的每一层代表”第几行”，选择列表是”这一行放哪列”。剪枝条件是同一列、对角线不能有皇后。

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  // cols[i] = 第 i 行的皇后放在第几列
  const cols: number[] = [];
 
  function isValid(row: number, col: number): boolean {
    for (let r = 0; r < row; r++) {
      const c = cols[r];
      // 同列
      if (c === col) return false;
      // 同对角线（行差 == 列差）
      if (Math.abs(c - col) === row - r) return false;
    }
    return true;
  }
 
  function backtrack(row: number): void {
    // 终止：放完 n 行
    if (row === n) {
      const board = cols.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1));
      result.push(board);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!isValid(row, col)) continue; // 剪枝
      cols.push(col);       // 做选择
      backtrack(row + 1);   // 递归
      cols.pop();           // 撤销
    }
  }
 
  backtrack(0);
  return result;
}

经典题四：子集

LeetCode 78。给定不含重复数字的数组，返回所有子集。

和排列的区别：子集不关心顺序，且长度可以任意。所以不需要 used 数组，只需要一个 start 索引保证不回头选前面的元素：

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const track: number[] = [];
 
  function backtrack(start: number): void {
    // 注意：子集题每个节点都是解，不需要终止条件
    result.push([...track]);
    for (let i = start; i < nums.length; i++) {
      track.push(nums[i]);
      backtrack(i + 1);
      track.pop();
    }
  }
 
  backtrack(0);
  return result;
}

关键差异：排列题在叶子节点收集解，子集题在每个节点都收集解（包括空集）。

四类题的模板差异

题型	选择列表	收集时机	剪枝方式
排列	所有未用过的元素	叶子节点	used 数组去重
组合	从 start 开始的元素	叶子节点	start 索引不回头
子集	从 start 开始的元素	每个节点	start 索引不回头
约束	满足约束的选择	叶子节点	isValid 函数

记忆方法：排列用 used，组合/子集用 start，约束题用 isValid。

什么时候用回溯

回到你自己笔记里的模式表，回溯对应的是这一行：

如果题目涉及：组合/排列/子集 → 回溯

更具体地，看到这些信号词就想回溯：

• “所有” + “合法” / “有效” → 括号生成、N 皇后
• “所有排列” / “所有组合” → 排列、组合
• “所有子集” / “所有方案” → 子集
• “是否可以” + “放置/分割/选择” → 分割回文串、单词搜索
• “满足约束” + “枚举” → 数独、图着色

和其他算法的区别

维度	回溯	动态规划	贪心
求什么	所有解 / 任意解	最优值	最优解
子问题	不重叠	重叠	贪心选择
复杂度	指数级	多项式	多项式
典型题	全排列	最长递增子序列	区间调度

一个判断技巧：问”有多少种”用 DP，问”列出所有”用回溯。 括号生成问”列出所有合法序列”——回溯；括号数量问”有几种”——DP（卡特兰数）。

优化技巧

1. 剪枝（Pruning）

最重要的优化。在递归前判断选择是否合法，不合法直接跳过，不进入子树。

// 不剪枝：生成所有再过滤
if (isValid(path)) result.push(path);
 
// 剪枝：生成时只走合法路径
if (!isValid(choice)) continue; // 不走进死路
backtrack(...);

括号生成题里 close > open 就是剪枝——不产生非法解，省掉整棵非法子树。

2. 排序 + 跳过重复

组合题里有重复元素时（如 [1,1,2]），先排序，然后跳过相邻重复：

nums.sort((a, b) => a - b);
// 在循环里
if (i > start && nums[i] === nums[i - 1]) continue;

3. 选择顺序

某些题（如 N 皇后）按列数从少到多的顺序探索，能更快碰到失败，减少搜索空间。

4. 约束传播

数独这类约束强的题，每次填一个数后立即更新相关格子的可用数字，缩小后续选择列表。

常见陷阱

1. 忘记撤销选择：只 push 不 pop，路径状态错乱，解全废。
2. 收集解时浅拷贝：result.push(path) 推的是引用，后面 path 改了，result 里的也变了。必须 result.push([...path]) 或 result.push(path.slice())。
3. 终止条件写错：排列题终止在 track.length === nums.length，子集题没有终止条件（每个节点都是解）。
4. n=0 的边界：括号生成 n=0 返回 [""]（一个空解），不是 []（无解）。卡特兰数 C_0 = 1 也印证了这点。
5. 剪枝条件写反：括号题里 close > open 表示”还能放的 > 比 < 多”，即”已放的 < 比 > 多”。写成 close >= open 会允许多余的 >，产生非法解。

复杂度分析

回溯是暴力枚举，复杂度一般很高：

题型	解的数量	时间复杂度
全排列	n!	O(n × n!)
子集	2^n	O(n × 2^n)
组合 C(n,k)	C(n,k)	O(k × C(n,k))
括号生成	C_n（卡特兰）	O(n × C_n) ≈ O(4^n/√n)
N 皇后	视 n 而定	O(n!)

空间复杂度：递归栈 O(n)，不计输出。计输出则乘以解的数量。

练习题单

按难度递增：

题目	类型	难度
17. 电话号码的字母组合	组合	中
77. 组合	组合	中
46. 全排列	排列	中
78. 子集	子集	中
39. 组合总和	组合+约束	中
22. 括号生成	约束	中
79. 单词搜索	约束	中
51. N 皇后	约束	困难
37. 解数独	约束	困难
131. 分割回文串	分割	中
93. 复原 IP 地址	分割	中

面试策略

1. 先说思路再写代码：讲清楚决策树、路径、选择列表、终止条件，再动手。
2. 先写骨架再填逻辑：先写 backtrack 函数签名和终止条件，再填 for 循环。
3. 先暴力再剪枝：如果剪枝条件想不清楚，先写不剪枝的版本（生成所有再过滤），再优化。
4. 跑测试时关注边界：空输入、单元素、n=0、n=1。

参考来源

• Backtracking Algorithm Common Patterns and Code Template — labuladong
• Understanding Backtracking Algorithms — AlgoCademy
• Backtracking Algorithm — GeeksforGeeks
• Backtracking — Wikipedia
• interviewing.io Learning Center

相关文章

• 算法解题流程：从读题到提交的七步 — 七步解题法
• 算法解题思路：边界条件与返回值 — 边界条件方法论
• 13. Generate Valid Angle Bracket Sequences — 括号生成实战题
• 8. Validate Properly Nested Brackets — 括号验证（栈），本文是生成版
• 贪心算法 — 对比贪心模式