递归、搜索与回溯算法实战
在算法面试和竞赛中，递归、搜索与回溯是高频考点。这类问题的核心在于构建决策树，并通过剪枝优化搜索空间。本文将通过六个经典题目，深入剖析暴搜（暴力搜索）的框架实现与细节处理。
1. 优美的排列
题目描述 给定一个整数 n，构造一个长度为 n 的排列，使得对于每个位置 i（1-based），满足 perm[i] % i == 0 或 i % perm[i] == 0。
算法思路 这是一个典型的回溯问题。我们需要枚举每个位置的数字，并检查是否满足条件。
决策树与剪枝
- 红色剪枝：如果当前分支已经使用过该数字，直接跳过。我们可以用一个
used数组标记。 - 紫色剪枝：检查当前位置 i 与候选数字 num 是否满足整除关系，不满足则剪枝。
代码实现
def countArrangement(n: int) -> int:
used = [False] * (n + 1)
def backtrack(index: int) -> int:
if index > n:
return 1
count = 0
for num in range(1, n + 1):
if not used[num] and (num % index == 0 or index % num == 0):
used[num] = True
count += backtrack(index + 1)
used[num] = False
return count
return backtrack(1)
2. N 皇后问题
题目描述 将 n 个皇后放置在 n×n 的棋盘上，使得任意两个皇后不能互相攻击。
算法原理 每一行只能放一个皇后。难点在于如何高效判断列和对角线冲突。
剪枝策略
- 列冲突：使用
col[j]标记第 j 列是否有皇后。 - 对角线冲突：主对角线由
row - col唯一确定，副对角线由row + col唯一确定。由于row - col可能为负数，需要加上偏移量 n。
代码实现
def solveNQueens(n: int) -> List[List[str]]:
res = []
board = [['.'] * n for _ in range(n)]
cols = [False] * n
diag1 = [False] * (2 * n) # row - col + n
diag2 = [False] * (2 * n) # row + col
def backtrack(row: int):
if row == n:
res.append([''.join(r) for r in board])
return
for col in range(n):
d1, d2 = row - col + n, row + col
if cols[col] or diag1[d1] or diag2[d2]:
continue
cols[col] = diag1[d1] = diag2[d2] = True
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
cols[col] = diag1[d1] = diag2[d2] = False
backtrack(0)
return res
3. 有效的数独
题目描述 判断一个 9x9 的数独是否有效，只需验证已填入的数字是否符合规则。
算法思路 虽然这题不是纯暴搜，但它是解数独的基础。我们需要用哈希表或数组记录每行、每列、每个 3x3 宫格内数字的出现情况。
映射关系
- 行：
row[i][num] - 列：
col[j][num] - 宫格：
box[i//3][j//3][num]
代码实现
def isValidSudoku(board: List[List[str]]) -> bool:
rows = [[False]*10 for _ in range(9)]
cols = [[False]*10 for _ in range(9)]
boxes = [[False]*10 for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] == '.':
continue
num = int(board[i][j])
box_idx = (i // 3) * 3 + (j // 3)
if rows[i][num] or cols[j][num] or boxes[box_idx][num]:
return False
rows[i][num] = cols[j][num] = boxes[box_idx][num] = True
return True
4. 解数独
题目描述 编写程序填充空格，使数独合法。
算法原理 这是有效的数独的扩展，需要使用 DFS 回溯。关键点是 DFS 函数返回布尔值，告诉上一层当前路径是否可行。
DFS 设计
- 遍历所有格子，遇到 '.' 尝试填 1-9。
- 如果填完所有格子，返回 True。
- 如果某一步无法填入任何数字，返回 False，触发回溯。
代码实现
def solveSudoku(board: List[List[str]]) -> None:
def is_valid(i, j, num):
for k in range(9):
if board[i][k] != '.' and board[i][k] == num:
return False
if board[k][j] != '.' and board[k][j] == num:
return False
box_i, box_j = 3 * (i // 3) + k // 3, 3 * (j // 3) + k % 3
if board[box_i][box_j] != '.' and board[box_i][box_j] == num:
return False
return True
def dfs(idx):
if idx == 81:
return True
i, j = divmod(idx, 9)
if board[i][j] != '.':
return dfs(idx + 1)
for num in map(str, range(1, 10)):
if is_valid(i, j, num):
board[i][j] = num
if dfs(idx + 1):
return True
board[i][j] = '.'
return False
dfs(0)
5. 单词搜索
题目描述 在二维字符网格中查找是否存在给定的单词。
算法思路 深度优先搜索（DFS）。从矩阵中每个字符开始，向上下左右四个方向递归匹配。
细节处理
- 避免重复路径：可以使用
visited数组，或者临时修改当前字符为特殊符号（如.），回溯时恢复。 - 方向映射：使用
dx,dy数组简化坐标计算。
代码实现
def exist(board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(i, j, k):
if not (0 <= i < m and 0 <= j < n) or board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
temp = board[i][j]
board[i][j] = '#' # 标记访问
for dx, dy in directions:
if dfs(i + dx, j + dy, k + 1):
return True
board[i][j] = temp # 回溯
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
6. 黄金矿工
题目描述 在一个网格中收集黄金，每次移动可以上下左右，但不能走回头路，也不能走值为 0 的格子。
算法思路 类似单词搜索，但目标是最大化收集的黄金总和。不需要找特定路径，而是找最大路径和。
关键点
- 不需要递归出口判断是否找到目标，而是更新全局最大值。
- 进入 DFS 就更新结果，因为每一步都可能是一个终点。
代码实现
def getMaximumGold(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
max_gold = 0
def dfs(i, j, current_gold):
nonlocal max_gold
max_gold = max(max_gold, current_gold)
val = grid[i][j]
grid[i][j] = 0 # 标记访问
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + dx, j + dy
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != 0:
dfs(ni, nj, current_gold + grid[ni][nj])
grid[i][j] = val # 回溯
for i in range(m):
for j in range(n):
if grid[i][j] != 0:
dfs(i, j, grid[i][j])
return max_gold
7. 不同路径 III
题目描述 从起点出发，经过所有非障碍且非起点的格子恰好一次，到达终点。
算法思路 统计总共有多少个可走格子（包括起点和终点）。DFS 过程中记录已走步数，当步数等于总数且停在终点时计数加一。
优化
- 提前统计空格子数量，减少无效搜索。
- 到达终点时立即返回，无需继续探索。
代码实现
def uniquePathsIII(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
start_x, start_y = 0, 0
empty_count = 1 # 包含起点
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
continue
elif grid[i][j] == 1:
start_x, start_y = i, j
else:
empty_count += 1
def dfs(x, y, count):
if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == -1:
return 0
if grid[x][y] == 2:
return 1 if count == empty_count else 0
grid[x][y] = -1
res = dfs(x+1, y, count+1) + dfs(x-1, y, count+1) + \
dfs(x, y+1, count+1) + dfs(x, y-1, count+1)
grid[x][y] = 0
return res
return dfs(start_x, start_y, 1)
总结
回溯算法的核心在于'试错'与'回退'。在实际编码中，重点考察的是对细节的处理能力：
- 状态管理：如何高效地记录和使用过的状态（数组 vs 哈希表）。
- 剪枝优化：尽早发现不可行路径，减少搜索空间。
- 边界条件：特别是递归出口的判断和返回值的传递。
掌握这些模式后，面对类似的搜索问题就能快速构建出解决方案。