回溯算法入门到实战：用 JavaScript 讲透原理、步骤与模板

很多人第一次学回溯时，会觉得它像一种“暴力枚举的玄学写法”：代码里全是递归、数组 push / pop、还有各种 used、startIndex、Set。但只要你把它看成一棵决策树，整个思路就会一下子清晰很多。

回溯算法的本质：在决策树上做深度优先搜索；如果当前选择走不通，就撤销这一步，回到上一个状态继续试。

这篇文章会讲三件事：

回溯到底在解决什么问题，它和 DFS 是什么关系。
写回溯题时，应该按什么步骤把题面翻译成代码。
如何用 JavaScript 写出能过面试、也能自己复用的回溯模板。

回溯算法流程图

一句话口诀：先判断，再选择；选完递归；回来撤销。

一、什么是回溯算法？#

回溯（Backtracking）是一种通过试错来搜索所有可行解的方法。

它通常适合这类题：

要求找出所有方案。
需要从若干候选项中不断“选一个，再继续选下一个”。
每一步都会影响下一步可选范围。
一旦发现当前路径不合法，就应该立刻停止继续往下搜。

典型关键词包括：

全排列
组合
子集
棋盘放置
路径搜索
字符串切分
满足约束的所有解

回溯和 DFS 的关系#

很多人会把“回溯”和“DFS”混在一起。更准确地说：

DFS（深度优先搜索） 是一种搜索顺序。
回溯是一种“DFS + 撤销状态”的解题框架。

也就是说，回溯通常借助 DFS 来遍历整棵决策树，但它比普通 DFS 多了一个关键动作：撤销选择。

如果你把每次递归都看成“进入下一层决策”，那么回溯的核心动作就是这三步：

做选择。
递归进入下一层。
撤销刚才的选择。

二、把题目翻译成“决策树”#

几乎所有回溯题，都可以画成一棵树：

节点：当前已经做出的选择。
边：这一步新增的选择。
叶子节点：一个完整答案，或者一条失败路径。

比如在全排列问题里，[1, 2, 3] 的决策树可以理解成：

第一层决定第 1 个位置放谁。
第二层决定第 2 个位置放谁。
第三层决定第 3 个位置放谁。

全排列的决策树示意图

所以写回溯时，你其实一直在回答四个问题：

路径（path）是什么？ 当前已经选了哪些元素？
选择列表（choices）是什么？ 这一层还能选谁？
结束条件是什么？ 什么情况下说明找到答案了？
剪枝条件是什么？ 什么情况下可以直接停止，不必继续递归？

这四个问题想清楚，代码基本就出来了。

三、回溯的通用模板#

先看最常用的 JavaScript 模板：

1
function backtrack() {
2
  if (满足结束条件) {
3
    result.push(当前路径的拷贝);
4
    return;
5
  }
6

7
  for (const choice of 当前层可选项) {
8
    if (这个选择不合法) continue;
9

10
    做选择;
11
    backtrack(进入下一层);
12
    撤销选择;
13
  }
14
}

把它写成更贴近真实题目的样子：

1
function solve(nums) {
2
  const result = [];
3
  const path = [];
4

5
  function dfs() {
6
    if (path.length === nums.length) {
7
      result.push([...path]);
8
      return;
9
    }
10

11
    for (const num of nums) {
12
      if (当前不能选 num) continue;
13

14
      path.push(num);
15
      dfs();
16
      path.pop();
17
    }
18
  }
19

20
  dfs();
21
  return result;
22
}

模板里最重要的三个动作#

1. 做选择#

把当前元素加入路径，或者更新状态。

1
path.push(num);

2. 递归深入#

让下一层继续做决策。

1
dfs();

3. 撤销选择#

回到进入这一层之前的状态，否则会污染后续分支。

1
path.pop();

很多回溯题写错，不是因为递归没想明白，而是因为“撤销状态”没还原干净。

四、写回溯题的实践步骤#

下面是一套很适合面试和刷题时使用的实战步骤。

第 1 步：先问“这一层在决定什么”#

回溯最怕一上来就写代码。建议先停 30 秒，想一句话：

当前递归层，到底在决定哪个位置、哪一项、哪一行、哪一个选择？

例如：

全排列：当前层决定“当前位置放哪个数”。
子集：当前层决定“第 i 个数要不要选”。
N 皇后：当前层决定“当前行的皇后放在哪一列”。

第 2 步：定义状态变量#

回溯里最常见的状态变量就这几种：

状态	含义	常见场景
`path`	当前路径	排列、组合、子集
`result`	所有答案	所有回溯题
`used`	某个元素是否已使用	排列
`startIndex`	本层从哪里开始枚举	组合、子集
`row` / `col`	当前行列位置	棋盘问题
`Set` / `Map`	记录约束是否冲突	N 皇后、数独

第 3 步：写清结束条件#

结束条件决定“什么时候收集答案，什么时候停止递归”。

例如：

path.length === nums.length：找到一个完整排列。
sum === target：找到一个合法组合。
row === n：N 皇后已经放完最后一行。

第 4 步：枚举当前层的所有选择#

这一步对应模板里的 for 循环。你需要明确：

当前有哪些候选项？
哪些候选项不合法？
这些不合法的情况能否提前剪掉？

第 5 步：做选择、递归、撤销#

这是回溯最核心的固定动作：

1
path.push(choice);
2
dfs(...);
3
path.pop();

如果你还维护了别的状态，也要成对撤销：

1
used[i] = true;
2
dfs(...);
3
used[i] = false;

第 6 步：考虑剪枝#

剪枝的意思是：有些分支明知道不可能得到答案，就不要继续搜了。

常见剪枝方式：

当前和已经超过目标值。
当前皇后位置已经和已有皇后冲突。
候选数组已排序，后面的数只会更大，可以直接 break。

剪枝不会改变正确性，但会显著提升性能。

五、经典例题 1：全排列#

题目：给定一个不重复数组 nums，返回它的所有排列。

思路拆解#

path 表示当前已经排好的序列。
used[i] 表示 nums[i] 是否已被放进 path。
当 path.length === nums.length 时，得到一个完整排列。

JavaScript 实现#

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

6
  function dfs() {
7
    if (path.length === nums.length) {
8
      result.push([...path]);
9
      return;
10
    }
11

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

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

18
      dfs();
19

20
      used[i] = false;
21
      path.pop();
22
    }
23
  }
24

25
  dfs();
26
  return result;
27
}
28

29
console.log(permute([1, 2, 3]));
30
// [
31
//   [1, 2, 3], [1, 3, 2],
32
//   [2, 1, 3], [2, 3, 1],
33
//   [3, 1, 2], [3, 2, 1]
34
// ]

这题的关键点#

排列问题里，顺序不同算不同答案，所以需要 used。
每一层都要从头枚举整个 nums。
回来时一定要同时还原 used[i] 和 path。

复杂度#

时间复杂度：O(n * n!)
空间复杂度：O(n)

六、经典例题 2：组合总和#

题目：给定一个无重复正整数数组 candidates 和目标值 target，找出所有和为 target 的组合。每个数字可以重复使用。

思路拆解#

这题和排列不一样，顺序不重要，所以不能每层都从头开始枚举，否则会出现重复组合。

这里我们要多维护一个 startIndex：

本层只能从 startIndex 开始往后选。
如果一个数字可以重复使用，递归时仍然传 i。
如果一个数字只能用一次，递归时传 i + 1。

先把数组排序，就能利用“后面只会更大”来做剪枝。

JavaScript 实现#

1
function combinationSum(candidates, target) {
2
  const result = [];
3
  const path = [];
4
  candidates.sort((a, b) => a - b);
5

6
  function dfs(startIndex, sum) {
7
    if (sum === target) {
8
      result.push([...path]);
9
      return;
10
    }
11

12
    for (let i = startIndex; i < candidates.length; i++) {
13
      const num = candidates[i];
14
      const nextSum = sum + num;
15

16
      if (nextSum > target) break; // 剪枝：后面的数只会更大
17

18
      path.push(num);
19
      dfs(i, nextSum); // 还能重复使用当前元素
20
      path.pop();
21
    }
22
  }
23

24
  dfs(0, 0);
25
  return result;
26
}
27

28
console.log(combinationSum([2, 3, 6, 7], 7));
29
// [[2, 2, 3], [7]]

这题的关键点#

组合问题通常需要 startIndex 来避免重复。
排序之后，nextSum > target 可以直接 break，这是典型剪枝。
如果题目改成“每个数只能用一次”，那递归要改成 dfs(i + 1, nextSum)。

七、经典例题 3：N 皇后#

题目：把 n 个皇后放到 n x n 的棋盘上，使任意两个皇后都不能互相攻击。

思路拆解#

N 皇后是回溯题里非常经典的“约束搜索”：

每一层递归表示“当前要处理第几行”。
每一行只能放一个皇后。
不能和之前皇后出现在同一列、同一主对角线、同一副对角线。

为了快速判断冲突，我们用三个集合：

cols：记录哪些列已有皇后。
diag1：记录主对角线 row - col。
diag2：记录副对角线 row + col。

JavaScript 实现#

1
function solveNQueens(n) {
2
  const result = [];
3
  const board = Array.from({ length: n }, () => Array(n).fill("."));
4
  const cols = new Set();
5
  const diag1 = new Set();
6
  const diag2 = new Set();
7

8
  function dfs(row) {
9
    if (row === n) {
10
      result.push(board.map(line => line.join("")));
11
      return;
12
    }
13

14
    for (let col = 0; col < n; col++) {
15
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
16
        continue;
17
      }
18

19
      board[row][col] = "Q";
20
      cols.add(col);
21
      diag1.add(row - col);
22
      diag2.add(row + col);
23

24
      dfs(row + 1);
25

26
      board[row][col] = ".";
27
      cols.delete(col);
28
      diag1.delete(row - col);
29
      diag2.delete(row + col);
30
    }
31
  }
32

33
  dfs(0);
34
  return result;
35
}
36

37
console.log(solveNQueens(4));
38
// [
39
//   [".Q..", "...Q", "Q...", "..Q."],
40
//   ["..Q.", "Q...", "...Q", ".Q.."]
41
// ]

这题的关键点#

row 表示递归深度，每层只处理一行。
冲突检测要尽量 O(1)，否则会非常慢。
放置和撤销都要同步维护棋盘与三个集合。

八、什么时候该用 `used`，什么时候该用 `startIndex`？#

这是回溯初学者最容易混淆的地方。

场景	关键状态	原因
排列	`used`	因为每个位置都能重新从全部元素里挑一个
组合 / 子集	`startIndex`	因为顺序不重要，只能往后选，避免重复
棋盘搜索	行列 + 约束集合	因为重点不是“元素是否用过”，而是“位置是否合法”

你可以这样记：

顺序重要：大概率要 used
顺序不重要：大概率要 startIndex
有约束冲突：大概率要额外集合或标记数组

九、回溯题最常见的 5 个错误#

1. 忘记拷贝路径#

错误写法：

1
result.push(path);

正确写法：

1
result.push([...path]);

因为 path 是同一个数组对象，后面还会不断变化。

2. 撤销状态不完整#

比如你做选择时改了两个状态：

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

回来时也必须撤销两个状态：

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

3. 组合问题里递归起点写错#

如果顺序不重要，却每次都从 0 开始枚举，就会生成重复答案。

4. 剪枝条件写反#

剪枝只能“提前排除不可能的分支”，不能把合法答案剪掉。

5. 没想清楚“当前层决定什么”#

这是所有回溯 bug 的源头。如果层的含义不清楚，for 循环范围、结束条件、状态变量都会跟着乱。

十、如何判断一道题是不是回溯题？#

你可以快速做这几个判断：

题目是否要求所有解、全部方案、所有路径？
解是否由“一步步选择”构成？
当前选择是否会影响后续选择？
发现不合法后，是否应该立刻停止当前分支？

如果这四个问题里有 3 个以上答案是“是”，基本就可以往回溯上想。

十一、回溯的本质总结#

回溯并不神秘，它就是：

把问题抽象成一棵决策树。
用 DFS 一路往下试。
遇到答案就收集。
遇到死路就返回。
返回时撤销状态，继续尝试其他分支。

所以你真正要掌握的，不是“背几个模板”，而是这套固定思维：

当前层在决定什么？
当前路径记录了什么？
本层还能选什么？
什么时候结束？
哪些分支可以剪掉？
回来时要还原哪些状态？

当你能稳定回答这 6 个问题时，绝大多数回溯题都能自己写出来。

最后记住一句：回溯 = 决策树 + DFS + 撤销状态 + 剪枝。

一、什么是回溯算法？#

回溯和 DFS 的关系#

二、把题目翻译成“决策树”#

三、回溯的通用模板#

模板里最重要的三个动作#

1. 做选择#

2. 递归深入#

3. 撤销选择#

四、写回溯题的实践步骤#

第 1 步：先问“这一层在决定什么”#

第 2 步：定义状态变量#

第 3 步：写清结束条件#

第 4 步：枚举当前层的所有选择#

第 5 步：做选择、递归、撤销#

第 6 步：考虑剪枝#

五、经典例题 1：全排列#

思路拆解#

JavaScript 实现#

这题的关键点#

复杂度#

六、经典例题 2：组合总和#

思路拆解#

JavaScript 实现#

这题的关键点#

七、经典例题 3：N 皇后#

思路拆解#

JavaScript 实现#

这题的关键点#

八、什么时候该用 used，什么时候该用 startIndex？#

九、回溯题最常见的 5 个错误#

1. 忘记拷贝路径#

2. 撤销状态不完整#

3. 组合问题里递归起点写错#

4. 剪枝条件写反#

5. 没想清楚“当前层决定什么”#

十、如何判断一道题是不是回溯题？#

十一、回溯的本质总结#

八、什么时候该用 `used`，什么时候该用 `startIndex`？#