有些问题，我们找不到"一步到位"的巧妙解法，只能把所有可能都试一遍。比如：8 个皇后怎么摆在棋盘上互不攻击？一个数独怎么填？

面对这类问题，回溯（backtracking） 就是那把"系统地穷举"的工具。它不是瞎试，而是一条路走到黑，发现走不通就立刻回头换一条，并且用"剪枝"提前砍掉注定失败的分支。

这一课，我们掌握回溯的套路，理解它和 DFS（第 14 课）、DP（第 17 课）的关系。

一、回溯是什么：决策树上的深度优先 + 撤销

回溯的本质是在一棵"决策树"上做 DFS：

  • 每一步有若干选择（决策树分叉）
  • 走到底，看是不是一个解
  • 不是解（或走不通），就撤销上一步的选择，退回来试别的

关键在"撤销"——选择 → 递归 → 撤销选择。这三步是回溯的灵魂。

用"全排列"理解：把 [1,2,3] 的所有排列列出来。

决策树（以 [1,2,3] 为例）：
          []
      /   |   \
     1    2    3
    / \  / \  / \
   2  3 1  3 1  2
   |  | |  | |  |
   3  2 3  1 2  1
def permute(nums):
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):   # 走到头，得到一个排列
            result.append(path[:])
            return
        for i, n in enumerate(nums):
            if used[i]:              # 这个数用过了，跳过（剪枝）
                continue
            used[i] = True
            path.append(n)           # 选择
            backtrack(path, used)    # 递归
            path.pop()               # 撤销选择
            used[i] = False          # 撤销标记
    backtrack([], [False] * len(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]]

看这三行：

path.append(n)      # 做选择
backtrack(...)      # 深入下一层
path.pop()          # 撤销选择（回溯！）

这就是回溯的模板。"选择 → 递归 → 撤销"，几乎所有回溯题都是这个骨架。

二、回溯的通用模板

def backtrack(路径, 选择列表):
    if 满足结束条件:
        收集结果
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 新的选择列表)   # 深入
        撤销选择                          # 回溯

把模板背下来，套到具体题里，改三处：结束条件、选择列表、剪枝条件。

三、剪枝：提前砍掉没希望的分支

回溯是"暴力穷举"，如果不加约束，选择会爆炸式增长。剪枝就是在递归前先判断"这条路还有没有希望"，没希望就不走了。

全排列里 if used[i]: continue 就是一种剪枝——已经用过的数不再选。

再看一个更明显的例子——组合（从 [1,2,3,4] 里选 2 个，不讲顺序）：

def combine(n, k):
    result = []
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        # 剪枝：剩下的数不够凑满 k 个了，直接不试
        for i in range(start, n + 1):
            if n - i + 1 < k - len(path):   # 剩余不够 → 剪枝
                break
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return result

print(combine(4, 2))   # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

体会：if n - i + 1 < k - len(path): break 这句，把"根本凑不够"的分支直接砍掉，省了大量计算。剪枝越早、越狠，回溯越快。

四、经典应用

1. N 皇后（回溯的招牌题）

在 n×n 棋盘上放 n 个皇后，使它们互相不攻击（同行、同列、同对角线都不能有两个）。

def solve_n_queens(n):
    result = []
    # 用三个集合标记"哪些列/对角线被占了"（剪枝）
    cols = set()
    diag1 = set()   # 主对角线（左上→右下）：r - c 恒定
    diag2 = set()   # 副对角线（右上→左下）：r + c 恒定

    def backtrack(r, board):
        if r == n:                    # 放满 n 行，得到一个解
            result.append(["".join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r-c) in diag1 or (r+c) in diag2:
                continue              # 剪枝：这个位置会被攻击
            # 做选择
            board[r][c] = "Q"
            cols.add(c); diag1.add(r-c); diag2.add(r+c)
            backtrack(r + 1, board)   # 深入下一行
            # 撤销选择
            board[r][c] = "."
            cols.remove(c); diag1.remove(r-c); diag2.remove(r+c)

    board = [["."] * n for _ in range(n)]
    backtrack(0, board)
    return result

solutions = solve_n_queens(4)
print("4 皇后解的数量:", len(solutions))   # 2
for s in solutions:
    for row in s:
        print(row)
    print()

体会：用三个集合记录"被攻击的列/对角线"，把"这个位置能不能放"的判断变成 O(1)，这就是高效的剪枝。8 皇后有 92 个解，但剪枝后回溯依然很快。

2. 生成括号

给 n，生成所有合法的括号组合（如 n=3：((()))、(()())、(())()、()(())、()()()）。

def generate_parenthesis(n):
    result = []
    def backtrack(s, left, right):
        if len(s) == 2 * n:          # 用完所有括号
            result.append(s)
            return
        if left < n:                  # 还能加左括号
            backtrack(s + "(", left + 1, right)
        if right < left:              # 右括号不能比左括号多（剪枝）
            backtrack(s + ")", left, right + 1)
    backtrack("", 0, 0)
    return result

print(generate_parenthesis(3))

剪枝点：right < left——右括号永远不能超过左括号，否则就不合法了。这一步砍掉了大量非法分支。

五、回溯 vs DFS vs DP

回溯DFS（图遍历）DP
本质决策树上的 DFS + 撤销图上 DFS + visited记忆化填表
要撤销吗要（path.pop）不要（只标记 visited）不涉及
目标找所有解 / 一个解遍历 / 搜索求最优值
是否剪枝强依赖剪枝提速用 visited 避免重复用备忘录避免重复

记住：回溯是"在决策树上 DFS，并记得撤销选择"；它和 DFS 是亲戚（都是深度优先），但回溯多了"撤销"这一步。回溯和 DP 都能解一些组合问题，区别在于：回溯找"具体是哪些解"，DP 求"最优值是多少"。有些题两者可以互相转换（记忆化搜索就是它们的桥梁）。

六、复杂度小结

回溯的复杂度 = 决策树的大小（最坏是"指数级"，因为要穷举）。剪枝的目的，就是把实际遍历的分支数，从"理论最坏"压到"实际可行"。

问题最坏复杂度
全排列O(n!)
组合 C(n,k)O(C(n,k))
N 皇后O(n!)（剪枝后实际远小）

心法：回溯题一般不追求"多项式时间"，因为穷举本身就可能指数级。能做的是剪枝尽量狠，把 n 的可行范围推大。

七、动手时间 🎯

实验 1：全排列（看"选择→递归→撤销"）

def permute(nums):
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i, n in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(n)
            backtrack(path, used)
            path.pop()
            used[i] = False
    backtrack([], [False] * len(nums))
    return result

print(permute([1, 2, 3]))

实验 2：子集（所有组合）

给一个不含重复元素的数组，列出它的所有子集：

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])   # 每个节点都是一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

实验 3：剪枝效果对比（组合数）

把第 17 课的组合题，加/不加剪枝跑一遍，看时间差：

import time

def combine_no_prune(n, k):
    result = []
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return result

def combine_prune(n, k):
    result = []
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            if n - i + 1 < k - len(path):
                break
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return result

start = time.time(); a = combine_no_prune(20, 10); t1 = time.time() - start
start = time.time(); b = combine_prune(20, 10); t2 = time.time() - start
print(f"不剪枝: {round(t1,4)}s | 剪枝: {round(t2,4)}s | 结果数: {len(a)} == {len(b)}")

实验 4（挑战）：数独求解器

回溯 + 剪枝的终极应用——解数独：

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num or board[i][c] == num:
                return False
        # 检查 3x3 宫
        br, bc = (r // 3) * 3, (c // 3) * 3
        for i in range(3):
            for j in range(3):
                if board[br + i][bc + j] == num:
                    return False
        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:          # 空格
                    for num in range(1, 10):
                        if is_valid(r, c, num):   # 剪枝
                            board[r][c] = num
                            if backtrack():
                                return True
                            board[r][c] = 0    # 撤销
                    return False               # 1~9 都试了不行
        return True                            # 没有空格了

    backtrack()
    return board

board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
for row in solve_sudoku([r[:] for r in board]):
    print(row)

体会：数独就是"在 9×9 的决策空间里回溯 + 剪枝"，is_valid 是剪枝判断，board[r][c]=0 是撤销。你会看到，回溯能解数独这种"看起来要聪明"的问题——它靠的是系统地试 + 果断地砍。

八、小结

  1. 回溯 = 在决策树上 DFS + 撤销，万能模板就三步：做选择 → 递归 → 撤销选择。
  2. 剪枝 = 提前砍掉注定失败的分支，是回溯从"能用"到"好用"的关键。
  3. 回溯找"具体解"，DP 求"最优值"——两者通过记忆化搜索相通，回溯 + 剪枝是解 NP 难题（数独、N 皇后、组合）的主力。

到这里，算法与数据结构（第一阶段）+ 高级算法范式（第二阶段）就全部走完了。你已经掌握了复杂度、线性结构、哈希、排序、递归、二分、树、堆、图、贪心、DP、回溯——这是算法面试和算法思维的完整地基。

先别急着往后翻，把 N 皇后和数独亲手跑一遍，感受"系统地试 + 果断地砍"的威力——这是整个算法阶段最漂亮的收尾。

标签: none

添加新评论