递归与回溯：用状态空间解决组合问题

摘要

递归通过把问题拆成规模更小的同类问题来求解，回溯则在递归基础上探索选择空间，并在不满足条件时撤销选择。排列、组合、子集、路径和棋盘问题都可以使用这一思想。

本文介绍递归函数的基本结构、终止条件、调用栈、回溯模板和剪枝方法，并通过全排列、子集、组合总和、迷宫路径和 N 皇后等示例，建立解决组合搜索问题的通用方法。

一、背景与问题

有一类问题很难通过简单的循环直接解决：

• 从若干元素中选择不同组合。
• 生成所有排列。
• 在网格中寻找路径。
• 放置棋子并满足约束。
• 把一个问题拆成多个相同形式的子问题。

这些问题往往具有树形决策结构：

选择第一个元素
├─ 选择 A
│ ├─ 选择 B
│ └─ 选择 C
└─ 选择 B
├─ 选择 A
└─ 选择 C

递归负责沿着决策树向下探索，回溯负责在返回上一层时恢复状态。

二、核心概念

1. 递归的三个要素

一个正确的递归函数通常包含：

缺少基准条件会无限递归，状态不推进也会导致栈溢出。

2. 调用栈

递归调用会在调用栈中保存每一层的局部变量和返回位置：

solve(3)
→ solve(2)
→ solve(1)
→ 返回
→ 返回
→ 返回

递归深度较大时会消耗栈空间，可以考虑改写为显式栈或使用动态规划。

3. 回溯状态

回溯通常维护：

• 当前路径。
• 已使用元素。
• 当前下标。
• 剩余容量或目标值。
• 当前棋盘状态。

每次做出选择后递归，返回时撤销选择：

做选择
→ 递归探索
→ 撤销选择

4. 状态空间树

每个节点表示一个部分解，每条边表示一次选择。叶子节点可能是完整解，也可能是违反约束的失败解。

状态空间树可能指数增长，因此回溯通常需要剪枝。

5. 剪枝

剪枝是在确定当前路径不可能得到有效答案时提前停止：

• 当前和已经超过目标。
• 剩余元素不足。
• 当前棋盘冲突。
• 当前排序条件不满足。
• 同一层已经处理过相同选择。

剪枝的目标不是改变正确结果，而是减少无意义搜索。

三、工作原理

1. 通用回溯模板

backtrack(state):
if state 是完整解:
记录答案
return

for choice in 当前可选项:
if choice 不合法:
continue

做选择
backtrack(新状态)
撤销选择

模板中的关键是状态定义和合法性判断。

2. 排列与组合的区别

组合通常通过递归下标避免重复选择，排列通常使用 used 数组记录元素是否已使用。

3. 复杂度

排列数量通常为 n!，子集数量为 2^n，组合数量为 C(n, k)。回溯问题的复杂度经常是指数级，因此输入规模通常不会很大，或者需要强剪枝。

四、实战示例

1. 计算阶乘

def factorial(n: int) –> int:
if n < 0:
raise ValueError("n must be non-negative")
if n <= 1:
return 1
return n * factorial(n – 1)

基准条件是 n <= 1，递归规模每次减一。

2. 生成子集

def subsets(values: list[int]) –> list[list[int]]:
result: list[list[int]] = []
path: list[int] = []

def backtrack(index: int) –> None:
if index == len(values):
result.append(path.copy())
return

backtrack(index + 1)

path.append(values[index])
backtrack(index + 1)
path.pop()

backtrack(0)
return result

每个元素都有“选择”和“不选择”两条分支，因此共有 2^n 个子集。

3. 生成全排列

def permutations(values: list[int]) –> list[list[int]]:
result: list[list[int]] = []
path: list[int] = []
used = [False] * len(values)

def backtrack() –> None:
if len(path) == len(values):
result.append(path.copy())
return

for index, value in enumerate(values):
if used[index]:
continue

used[index] = True
path.append(value)
backtrack()
path.pop()
used[index] = False

backtrack()
return result

used 保证同一个元素不会在一条路径中重复使用。

4. 组合选择

def combinations(
values: list[int],
size: int,
) –> list[list[int]]:
result: list[list[int]] = []
path: list[int] = []

def backtrack(start: int) –> None:
if len(path) == size:
result.append(path.copy())
return

remaining = size – len(path)
max_start = len(values) – remaining

for index in range(start, max_start + 1):
path.append(values[index])
backtrack(index + 1)
path.pop()

backtrack(0)
return result

递归从 index + 1 开始，因此不会生成相同元素的反向组合。

5. 组合总和

def combination_sum(
candidates: list[int],
target: int,
) –> list[list[int]]:
candidates = sorted(set(candidates))
result: list[list[int]] = []
path: list[int] = []

def backtrack(start: int, remaining: int) –> None:
if remaining == 0:
result.append(path.copy())
return
if remaining < 0:
return

for index in range(start, len(candidates)):
value = candidates[index]
if value > remaining:
break

path.append(value)
backtrack(index, remaining – value)
path.pop()

backtrack(0, target)
return result

排序后，当当前值大于剩余目标时，可以直接停止当前循环，这就是一种剪枝。

6. 网格路径

def count_paths(grid: list[list[int]]) –> int:
rows = len(grid)
cols = len(grid[0]) if rows else 0
visited = [[False] * cols for _ in range(rows)]

def dfs(row: int, col: int) –> int:
if not (0 <= row < rows and 0 <= col < cols):
return 0
if grid[row][col] == 1 or visited[row][col]:
return 0
if row == rows – 1 and col == cols – 1:
return 1

visited[row][col] = True
total = (
dfs(row + 1, col)
+ dfs(row – 1, col)
+ dfs(row, col + 1)
+ dfs(row, col – 1)
)
visited[row][col] = False
return total

return dfs(0, 0)

visited 防止在当前路径中重复进入同一个格子，递归返回后要撤销标记，让其他路径可以继续使用该格子。

7. N 皇后

def solve_n_queens(n: int) –> list[list[str]]:
result: list[list[str]] = []
board = [["."] * n for _ in range(n)]
columns: set[int] = set()
diagonals: set[int] = set()
anti_diagonals: set[int] = set()

def backtrack(row: int) –> None:
if row == n:
result.append(["".join(line) for line in board])
return

for col in range(n):
diagonal = row – col
anti_diagonal = row + col

if (
col in columns
or diagonal in diagonals
or anti_diagonal in anti_diagonals
):
continue

board[row][col] = "Q"
columns.add(col)
diagonals.add(diagonal)
anti_diagonals.add(anti_diagonal)

backtrack(row + 1)

board[row][col] = "."
columns.remove(col)
diagonals.remove(diagonal)
anti_diagonals.remove(anti_diagonal)

backtrack(0)
return result

通过集合快速判断列和对角线是否冲突，避免每次扫描整张棋盘。

五、常见问题与实践建议

1. 为什么回溯结果要使用 path.copy()？

因为递归过程中会不断修改同一个 path。如果直接把 path 放入结果，后续撤销操作会同时改变已经保存的结果。

2. 为什么递归返回后必须撤销状态？

不撤销会把上一条路径的选择带到下一条路径，导致结果错误。撤销是回溯区别于普通递归的关键。

3. 如何避免重复组合？

组合问题递归时传递下一个起始位置；排列问题使用 used 记录当前路径已经选择的元素；有重复输入时还要跳过同层重复值。

4. 剪枝应该放在哪里？

尽量在做选择前判断当前选择是否可能成功。越早剪枝，后续递归分支越少。

5. 什么时候不适合使用回溯？

当输入规模较大、状态大量重复或子问题具有重叠结构时，纯回溯可能指数爆炸。可以考虑动态规划、记忆化搜索、贪心或数学方法。

六、进阶思考

1. 回溯与动态规划

回溯探索所有可能路径，动态规划保存重复子问题结果：

回溯：强调搜索路径和约束
动态规划：强调状态转移和重复利用

当不同搜索路径会到达同一个状态时，可以加入缓存。

2. 记忆化搜索

from functools import lru_cache

@lru_cache
def climb_stairs(n: int) –> int:
if n <= 2:
return n
return climb_stairs(n – 1) + climb_stairs(n – 2)

缓存避免重复计算，但会占用额外空间。

3. 状态压缩

如果状态只包含若干布尔选择，可以使用整数位表示，减少复制和比较成本。状态压缩常用于子集、棋盘和图搜索。

4. 搜索顺序

先处理约束更严格的选择，通常更容易尽早发现冲突，从而产生更强剪枝。N 皇后、数独和排班问题都可以利用这一原则。

结论

递归负责拆解同类子问题，回溯负责在选择空间中探索并恢复状态。理解基准条件、状态定义、选择、递归和撤销五个环节后，可以解决子集、排列、组合、路径和棋盘等问题。

面对指数级搜索，要通过排序、集合、边界判断、记忆化和更合理的搜索顺序进行剪枝。下一步可以继续学习动态规划，理解如何把重复子问题的结果保存下来。

参考资料