回溯与剪枝
回溯（Backtracking）是暴力搜索的"剪枝"版本——尝试所有可能，发现此路不通就退回上一步。剪枝越早，效率越高
🧭 走迷宫——试错的艺术
你走进一个迷宫，手里没有地图。怎么找到出口？
一个直观的方法是：一直往前走，遇到岔路口选一条路，如果走到死胡同就退回来，选另一条路。
这就是回溯（Backtracking）——穷举所有可能的路径，走不通就”退回去”（这就是”回溯”这个名字的来源）。
🚶 类比：在陌生小区找朋友家
你去一个从没去过的老小区找一个朋友。小区里的楼没有编号（或者编号混乱）。
你的策略：
- 选了 3 号楼，上到 6 楼敲门——不是，也没人知道朋友住哪
- 退出来，试 5 号楼——还不是
- 退出来，试 7 号楼——找到了！
这就是回溯——你不断地”尝试→失败→退回→尝试下一个”。
如果朋友告诉过你”我住的小区最里面那栋”——你就可以先排除外面的楼，先去最里面试。这就是剪枝——利用已知信息减少尝试的次数。
🔄 回溯的通用框架
回溯几乎总是可以用递归实现，有一个固定的模板：
def backtrack(当前状态, 选择列表, 结果集):
if 满足结束条件:
结果集.add(当前状态的副本)
return
for 每个选择 in 选择列表:
if 选择不合法或会被剪枝:
continue
# 做选择
记录选择
更新状态
# 递归到下一层
backtrack(新状态, 缩小后的选择列表, 结果集)
# 撤销选择（回溯的关键！）
撤销选择
恢复状态
关键的”三步曲”：
1. 做选择（尝试当前可能性）
2. 递归（进入下一层，继续尝试）
3. 撤销选择（"退回去"，试另一个可能性）
♟️ 经典案例：N 皇后问题
在 N×N 的棋盘上放置 N 个皇后，使得它们不能互相攻击——即任意两个皇后不在同一行、同一列、同一对角线上。
问题分析
- 每行必须放一个皇后（不然棋盘上放不满 N 个）
- 每次决定”这一行的皇后应该放在哪一列”
回溯解法
def solve_n_queens(n):
result = []
cols = set() # 已经占用的列
diag1 = set() # 已经占用的主对角线（row - col）
diag2 = set() # 已经占用的副对角线（row + col）
def backtrack(row, board):
# 结束条件：所有行都放好了
if row == n:
result.append(board[:]) # 找到一个解
return
# 尝试在当前行的每一列放皇后
for col in range(n):
# 剪枝：如果这一列或对角线已经被占用
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# 做选择：在 (row, col) 放皇后
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
board.append(col) # board[row] = col
# 递归到下一行
backtrack(row + 1, board)
# 撤销选择：拿走皇后
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
board.pop()
backtrack(0, [])
return result
4 皇后的搜索过程示意
第 0 行：尝试 col=0
[Q . . .] → cols={0}, diag1={0}, diag2={0}
第 1 行：尝试 col=0→被占，col=1→被 diag1(0) 排除，col=2→可以
[Q . . .]
[. . Q .]
第 2 行：col=0,1,2,3 都不行 → 回溯！
第 1 行：尝试 col=3 → 可以
[Q . . .]
[. . . Q]
第 2 行：col=1 → 可以
[Q . . .]
[. . . Q]
[. Q . .]
第 3 行：col=0,1,2,3 都不行 → 回溯！
……继续尝试……
找到的一个解：
[. Q . .]
[. . . Q]
[Q . . .]
[. . Q .]
💡 剪枝的效果：N 皇后中，如果是纯暴力（不考虑任何冲突），搜索空间是 N^N。加入列限制后，缩减到 N!。再加入对角线限制，实际搜索空间远小于 N!。这就是剪枝的力量——越早剪掉不可能的分支，搜索越快。
🧩 另一个经典：全排列
生成一个数组的所有排列，回溯的思路非常自然：
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:]) # 所有元素都用完了
return
for i in range(len(remaining)):
# 做选择：把 remaining[i] 加入路径
path.append(remaining[i])
new_remaining = remaining[:i] + remaining[i+1:]
# 递归
backtrack(path, new_remaining)
# 撤销选择
path.pop()
backtrack([], nums)
return result
print(permute([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
✂️ 剪枝技巧
剪枝（Pruning）是回溯最关键的性能优化——越早排除不可能的分支，搜索越快。
常见剪枝策略
# 1. 可行性剪枝——当前选择已经不可能得到合法解了
def can_place(board, row, col):
# 检查列、对角线是否可用
pass
# 2. 最优性剪枝——就算继续也不可能比已知最优解更好
def backtrack(...):
if current_cost >= best_cost:
return # 已经比已知解差了，剪枝！
# 3. 对称性剪枝——利用问题的对称性减少搜索
# 例如 N 皇后：第一行只需要试一半的列，结果乘 2
# 4. 预排序——先尝试"可能性更少"的分支
# 数独中，先填"可选数字最少"的格子——这叫"最少剩余值启发式"
剪枝前后对比（4 皇后）
无剪枝：尝试所有 C(16,4) × 4! 种摆放 → 回溯
有剪枝（行列限制）：尝试 4! = 24 种摆法
有剪枝（+对角线限制）：只需要尝试 2 种摆法（只有 2 个解）
剪枝的本质：利用问题约束条件，尽早判断”这条路走不通”。
⚔️ 回溯 vs 其他算法
| 算法 | 思想 | 时间复杂度 | 空间复杂度 | 应用 |
|---|---|---|---|---|
| 回溯 | 尝试→递归→撤销，剪枝优化 | 通常指数级 | O(深度) | 排列组合、N 皇后、数独 |
| DP | 记住子问题答案，避免重复 | 多项式 | 可大可小 | 背包、LCS |
| 贪心 | 每步选局部最优 | 通常线性 | O(1) | 活动选择、哈夫曼 |
回溯 vs DP 的关联：
有时回溯 + 记忆化 = DP。比如计算爬楼梯：
- 纯回溯：O(2^n)——大量重复计算
- 回溯 + memo：O(n)——这不就是 DP 吗？
- 所以 DP 可以看作是”带记忆化的回溯”。
🎯 回溯的典型应用场景
| 问题 | 回溯思路 | 剪枝方式 |
|---|---|---|
| N 皇后 | 每行放一个，尝试所有列 | 行列对角线冲突 |
| 数独 | 每个空格试 1-9 | 行/列/宫格已存在数字 |
| 全排列/组合 | 选一个元素加入路径 | 已选元素不再选 |
| 子集和 | 选或不选当前数字 | 和超过目标就剪 |
| 图着色 | 每个顶点试颜色 | 相邻顶点颜色冲突 |
| Sudoku | 空格填数字 | 行/列/3x3 约束 |
📝 小结
| 概念 | 一句话 |
|---|---|
| 回溯（Backtracking） | 尝试→递归→撤销——走不通就退回来 |
| 剪枝（Pruning） | 提前排除不可能的分支——越早越有效 |
| 回溯三步曲 | 做选择 → 递归 → 撤销选择 |
| 可行解 vs 最优解 | 回溯能找到所有解或最优解 |
| 和 DP 的关系 | 回溯 + 记忆化 = DP |
| 时间复杂度 | 通常指数级——但剪枝能大幅优化 |
🎯 小练习：用回溯解决”组合之和”问题——给定数组
[2, 3, 6, 7]和目标值7，找出所有和为 7 的组合（每个数字可以使用无限次）。
为什么先学这个？ 理解了各种算法设计思想后，最后来学习如何”评价”算法的效率——时间复杂度与大 O。