12.2 回溯
岔路不会替你保存状态
一份回溯实现应先回答四个问题：
- 当前路径保存了什么状态；
- 下一步有哪些候选选择；
- 哪些约束可以提前拒绝候选；
- 到达什么条件时，当前路径构成一个结果。
若使用可变路径，递归返回后必须撤销本层修改。保存结果时也要复制路径，否则所有结果可能指向同一个最终列表。
三个可执行的例子
n 必须是非负整数。另两个函数接收可迭代对象，排序副本后按值去重；元素的排序与相等关系应一致，不能混入 NaN 或无法互相比较的类型。输出列表只做浅复制，仍引用原元素；相等的不同对象会被视为同一个值。
def solve_n_queens(n):
if not isinstance(n, int):
raise TypeError("n must be an integer")
if n < 0:
raise ValueError("n must be non-negative")
solutions = []
columns = set()
descending = set() # row - column
ascending = set() # row + column
placement = []
def search(row):
if row == n:
solutions.append([
"." * column + "Q" + "." * (n - column - 1)
for column in placement
])
return
for column in range(n):
down = row - column
up = row + column
if (
column in columns
or down in descending
or up in ascending
):
continue
placement.append(column)
columns.add(column)
descending.add(down)
ascending.add(up)
search(row + 1)
ascending.remove(up)
descending.remove(down)
columns.remove(column)
placement.pop()
search(0)
return solutions
def unique_permutations(values):
items = sorted(values)
used = [False] * len(items)
path = []
result = []
def search():
if len(path) == len(items):
result.append(path.copy())
return
for index, value in enumerate(items):
if used[index]:
continue
if (
index > 0
and items[index] == items[index - 1]
and not used[index - 1]
):
continue
used[index] = True
path.append(value)
search()
path.pop()
used[index] = False
search()
return result
def unique_subsets(values):
items = sorted(values)
path = []
result = []
def search(start):
result.append(path.copy())
for index in range(start, len(items)):
if index > start and items[index] == items[index - 1]:
continue
path.append(items[index])
search(index + 1)
path.pop()
search(0)
return result
if __name__ == "__main__":
assert len(solve_n_queens(4)) == 2
assert solve_n_queens(1) == [["Q"]]
assert solve_n_queens(0) == [[]]
assert unique_permutations([1, 1, 2]) == [
[1, 1, 2],
[1, 2, 1],
[2, 1, 1],
]
assert unique_permutations([]) == [[]]
assert unique_subsets([1, 2, 2]) == [
[],
[1],
[1, 2],
[1, 2, 2],
[2],
[2, 2],
]
assert unique_subsets([]) == [[]]
print("回溯检查通过")这三个函数都把空输入的组合语义定为“一个空选择”，所以返回 [[]]，而不是“没有解”。N 皇后的 n=0 也沿用该约定。项目若采用其他定义，应在接口和测试中同时改变。
N 皇后：把扫描改成集合约束
每行只放一个皇后，因此路径只需记录各行选中的列。两个皇后冲突，当且仅当：
- 列相同；
row - column相同，位于同一条下降对角线；row + column相同，位于同一条上升对角线。
三个集合让一次冲突检查的平均成本接近 O(1)，避免每次重新扫描之前所有行。做选择时加入列和两条对角线，递归返回后按相反次序删除。顺序不是数学要求，却便于逐项核对状态恢复。
忽略对角线约束，各层的部分列排列数之和是 O(n!)。但本实现每个非叶节点仍扫描 n 列，因此搜索时间的一个保守上界是 O(n·n!)，不能只看叶节点数。若有 S 个解，构造并保存棋盘另需 Θ(S·n²) 时间和空间；搜索路径、集合和栈另占 O(n)。这里采用集合操作期望 O(1) 的计数模型。
全排列：重复值只在同层跳过
对排序后的 [1, 1, 2]，两个 1 在值上没有区别。条件：
items[index] == items[index - 1] and not used[index - 1]表示“同一层里，前一个相同值还没有被选，就不从后一个副本开一棵等价分支”。若前一个副本已经在当前路径中，后一个仍可继续使用，因此 [1, 1, 2] 不会被误删。
这条判断必须同时依赖排序与 used。只写“相邻相等就跳过”会漏掉合法排列；不排序则无法把同值候选放在一起。
若 n 个值互异，输出有 n! 个排列，每份结果长度 n，仅复制输出就需要 Θ(n·n!) 时间和空间。回溯无法突破输出规模。该实现每层还会扫描整个输入；大量重复值时，不能只按输出份数估算运行时间，例如 n 个相同值只有一个排列，候选扫描仍需 Θ(n²)。不计结果列表，排序副本、路径、used 和递归栈合计 O(n) 空间。
子集：start 消除位置重排
子集不区分选择顺序。递归参数 start 只允许向后选位置，因此 [1, 2] 与 [2, 1] 不会各生成一次。
去重条件 index > start 很关键：它只跳过同一递归层的相等候选。进入更深一层后，第二个 2 仍可被选中，才能生成 [2, 2]。
n 个互异元素有 2^n 个子集，输出全部子集的元素总数是 Θ(n·2^n)。剪枝只能删除不可能或重复分支，不能让“列出所有结果”变成多项式输出。不计结果列表，子集搜索也只保留 O(n) 的副本、路径和栈。三个实现的递归深度都可达 n，大输入会先受 Python 递归深度或结果内存限制。
什么时候剪枝才安全
剪枝必须来自可证明的约束。例如所有候选数都为非负时，当前和已经超过目标，可以停止向下搜索；若候选允许负数，后续元素可能把总和降回来，同一剪枝就不再正确。
实践中先写一个小规模、容易验证的版本，再逐条加入剪枝，并用暴力枚举作 oracle。性能理由不能替代正确性证明。Stanford 的回溯课程也从排列与皇后约束讨论这种搜索方式。
常见故障与定位
| 症状 | 先检查什么 |
|---|---|
| 所有结果最后都相同 | 存入结果时是否复制 path |
| 后续分支莫名缺少候选 | 递归返回后是否撤销集合、used 与路径 |
| 重复排列仍出现 | 输入是否先排序；是否只跳过同层重复 |
[2, 2] 子集消失 | 去重条件是否误写成无条件跳过相邻值 |
| N 皇后漏解 | 两条对角线是否分别使用 row-col 与 row+col |
| 剪枝后答案变少 | 剪枝前提是否对所有剩余候选成立 |
动手观察选择树
- 画出
unique_permutations([1, 1, 2])的前三层，标出被跳过的同层分支。 - 把 N 皇后的三个集合改成布尔数组，写清索引平移。
- 为子集函数加入固定长度 k，在哪一层能根据剩余元素数提前停止？
- 用
itertools.permutations和集合给随机短输入做 oracle。 - 设计一个含负数的子集和例子，反驳“当前和超过目标就停止”的错误剪枝。
走出选择树
回溯的核心不是一段万能模板，而是让状态变化成对出现：做选择、递归、撤销。选择树通常仍然很大；约束只删除已经证明不可能或重复的分支，输出规模则给出了无法绕开的下界。
若许多不同路径反复抵达同一个状态，继续裸回溯会浪费工作。下一章进入 动态规划，学习如何定义状态并复用子问题答案。