递归、搜索与回溯算法实战：从决策树到经典题目解析

剪枝策略

• 列冲突：使用 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)

总结

回溯算法的核心在于'试错'与'回退'。在实际编码中，重点考察的是对细节的处理能力：

1. 状态管理：如何高效地记录和使用过的状态（数组 vs 哈希表）。
2. 剪枝优化：尽早发现不可行路径，减少搜索空间。
3. 边界条件：特别是递归出口的判断和返回值的传递。

掌握这些模式后，面对类似的搜索问题就能快速构建出解决方案。