第12章：回溯（Backtracking）
Vol 2：算法森林探险 · 回溯特辑
元数据卡 | 难度: 进阶 | 前置: 分治、递归 | 关键词: 回溯三要素·N皇后·全排列·子集·剪枝 | 预计阅读: 50 分钟
分治是把问题切成独立的小块。但很多问题不能切——你需要试遍所有可能，走不通就回头。老陈用树枝在地上画了一条岔路，走几步打个叉，退回路口重走："回溯就是走不通回头。"
回溯模板——所有问题同一个灵魂
def backtrack(路径, 选择列表):
if 满足终止条件: # 目标
result.append(路径)
return
for 选择 in 选择列表:
if 不满足约束条件: # 约束/剪枝
continue
做选择 # 路径.append(选择)
backtrack(新路径, 新选择列表)
撤销选择 # 路径.pop()三要素： 选择（每步有几种选项）、约束（什么选择非法）、目标（什么时候找到解）。
2.1 N 皇后
在 N x N 棋盘上放 N 个皇后，不冲突。一行一行放。
def solve_n_queens(n):
result = []
board = [-1] * n
def is_safe(row, col):
for r in range(row):
c = board[r]
if c == col or abs(r - row) == abs(c - col):
return False
return True
def backtrack(row):
if row == n:
result.append(
["." * col + "Q" + "." * (n - col - 1) for col in board]
)
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1)
board[row] = -1
backtrack(0)
return result
solutions = solve_n_queens(4)
print(f"解数量: {len(solutions)}")
for sol in solutions:
for row in sol:
print(row)
print()运行步骤： 保存为 nqueens.py，执行 python nqueens.py。预期输出： 4 皇后有 2 个解。
为什么用一维数组？ 每行一个皇后。board[row]=col 比二维数组简洁。对角线冲突用 abs(r-row)==abs(c-col)——行差等于列差时在同一对角线。
2.2 全排列
顺序重要——[1,2,3] 和 [1,3,2] 不同。每步选没用过的元素。
def permute(nums):
result, path, used = [], [], [False] * len(nums)
def backtrack():
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack()
path.pop()
used[i] = False
backtrack()
return result
print(permute([1, 2, 3]))运行步骤： 保存为 permute.py，执行 python permute.py。预期输出： 6 个排列。
去重版本： 先排序，加 if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue。相同元素只有前一个被用了后一个才能用，避免重复排列。
2.3 子集
[1,2] 和 [2,1] 算同一个。每次只从当前元素后面选。
def subsets(nums):
result, path = [], []
def backtrack(start):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return result
print(subsets([1, 2, 3]))运行步骤： 保存为 subsets.py，执行 python subsets.py。预期输出： [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
模板差异： 全排列用 used[]（顺序重要），子集用 start 指针（顺序不重要，只从后面选）。
常见陷阱
回溯复杂度通常是指数级的。N 皇后 n!、全排列 n!、子集 2^n。剪枝加速但不改最坏情况。
撤销操作是大多数 bug 的来源——每写一个 backtrack 立即写撤销。 存入 result 要拷贝 path。
旅人笔记
- N 皇后是全排列的约束版本。 这一句就揭示了回溯本质：选择 + 约束 + 目标。
- 剪枝不是优化，是灵魂。 没有剪枝的回溯只是慢一点的暴力枚举。
一句话：分治切到单，回溯记三选，剪枝是关键。
下一站预告
分治和回溯只是热身。如果子问题高度重叠，分治会退化——这时需要把子问题答案存起来避免重复计算。
第 13 章：动态规划。 从递归到记忆化搜索再到 DP 表格。整个 DS&A 卷的巅峰之章。