回溯与剪枝 (Backtracking)
TL;DR
回溯 = 带撤销的 DFS：在解空间树上深度优先搜索，发现当前路径不可能通向合法解就回退。它本身是指数级的，真正决定能不能跑完的是剪枝——可行性剪枝（约束不满足直接返回）、最优性剪枝（不可能优于已知最优）、重复等价剪枝（同层同值跳过）、下界剪枝（分支限界）。本章给状态机模板、四类剪枝的判定写法、N 皇后/子集/全排列三组带剪枝的实现（Go + Python），以及"什么情况下该换成 DP / 分支限界 / 随机化"的判断。
读完应能：
- 写出回溯万能模板：
is_valid → apply → recurse → undo，并说清哪些状态需要显式撤销。 - 按"可行性 / 最优性 / 重复等价 / 下界"四类给任意回溯题设计剪枝。
- 处理两类经典坑：重复元素去重、引用 vs 值拷贝的撤销语义。
- 判断回溯 vs DP / 分支限界 / 迭代加深的适用边界。
一、模型与模板
solve(state):
if is_terminal(state): record(state); return
for choice in choices(state):
if is_valid(choice):
apply(choice) # 修改状态 (要能撤销)
solve(next_state)
undo(choice) # 撤销: 不撤销 = 泄漏状态
三个必须想清楚的点：
- 状态定义：
(已选集合, 剩余约束, 当前目标函数值)——状态冗余会导致重复搜索； - 展开顺序：先做约束最强的分支（MRV 启发式），把失败剪枝提前；
- 终止条件：叶子（记录）或剪枝点（提前返回）。
note
回溯的复杂度 = 解空间大小 × 剪枝收益。纯 N 皇后 $O(n!)$；加列/对角线剪枝后常数骤降，但渐近仍是指数——剪枝优化的是"实际运行的规模"，不改变指数阶。
二、四类剪枝
| 剪枝 | 判定写法 | 典型例子 |
|---|---|---|
| 可行性剪枝 | 剩余资源 < 所需最小值 | 组合总和：剩余预算 < 最小候选值即返回 |
| 最优性剪枝 | 当前值 + 乐观上界 ≤ 已知最优 | 旅行商、最大团 |
| 重复等价剪枝 | 排序后同层跳过相同值 | 含重复元素的全排列/子集 |
| 下界剪枝（分支限界） | 下界 ≥ 当前上界即剪 | 0/1 背包分支限界 |
重复等价剪枝的正确姿势
# 组合: 同层不重复选相同值
def dfs(start, path):
record(path)
for i in range(start, n):
if i > start and a[i] == a[i-1]: # 同层跳过, 不是跨层
continue
dfs(i + 1, path + [a[i]])
warning
去重只看"同层"：i > start and a[i] == a[i-1] 是组合去重；全排列去重要用 used[i-1] == False（前一个相同值未被使用，说明本层已展开过它）。把两者写反是经典 bug。
三、经典问题
3.1 N 皇后
按行放皇后，用 cols / diag1(i+j) / diag2(i-j) 三个集合 O(1) 判冲突：
func totalNQueens(n int) int {
cols, d1, d2 := make([]bool, n), make([]bool, 2*n), make([]bool, 2*n)
var dfs func(r int) int
dfs = func(r int) int {
if r == n { return 1 }
cnt := 0
for c := 0; c < n; c++ {
if cols[c] || d1[r+c] || d2[r-c+n] { continue }
cols[c], d1[r+c], d2[r-c+n] = true, true, true
cnt += dfs(r + 1)
cols[c], d1[r+c], d2[r-c+n] = false, false, false
}
return cnt
}
return dfs(0)
}
3.2 子集 / 组合 / 排列
- 子集：每个元素选/不选（$2^n$）；
- 组合：
for i in range(start, n)天然有序，剪掉排列冗余； - 排列：
used[]数组，可剪对称（首位固定一半）。
四、回溯的边界：什么时候别用
| 场景 | 换什么 | 原因 |
|---|---|---|
| 重叠子问题 | DP（见 dp.md） | 回溯会重复计算同一状态 |
| 只要一个最优值、可行解很多 | 分支限界 / 贪心近似 | 剪枝可加下界 |
| 深度远大于宽度、答案在浅层 | 迭代加深 IDDFS | 省内存、先出解 |
| 变量数巨大（>10^4） | CP-SAT / 整数规划 | 手写回溯规模不够 |
五、易错清单
- 撤销不完整：
path = path + [x]（新对象）不需撤销；path.append(x)必须配对path.pop()； - 去重条件写错层级：同层 vs 跨层的
used语义（见上）； - 剪枝顺序：先做可行性（便宜）再做最优性（要维护全局最优）；
- 状态污染：数组/集合作为状态要深拷贝或用"应用-撤销"对。
六、一页速查
模板: is_valid → apply → recurse → undo (带撤销 DFS)
剪枝: 可行性 / 最优性 / 重复等价 / 下界
去重: 组合=同层跳过; 排列=used[i-1]==False
启发式: 先展开约束最强的分支 (MRV)
换路: 重叠子问题→DP / 只要最优值→分支限界 / 深树浅解→IDDFS
下一篇: 分支限界。