回溯法（Backtracking）是一种系统搜索问题解的方法，核心思想是：从初始状态出发，按照一定规则逐步尝试构造解；当发现当前选择无法得到有效解时，就撤销上一步甚至多步的选择，换一条路径继续尝试。
它本质上是 深度优先搜索 + 剪枝 + 状态重置，常用来解决“搜索所有解”“搜索任意一个解”“在约束条件下求最优解”的问题。

一、回溯法的基本概念

1. 解空间

一个问题所有可能的解构成的集合，称为该问题的解空间。

例如：

  • 求集合 {1,2,3} 的全排列，解空间由 3! = 6 个排列组成；
  • 求 n 个元素的子集，解空间大小为 2^n；
  • n 皇后问题，解空间大小为 n! 左右。

回溯法通常将解空间组织成一棵树，称为解空间树，然后在树上进行深度优先搜索。

2. 两类典型解空间树

  • 子集树：每个元素有“选”或“不选”两种可能，例如子集问题、0/1背包问题。
    如果问题规模为 n，子集树最多有 2^n 个叶子节点。
  • 排列树：每个位置从剩余元素中选择一个，例如全排列、旅行商问题、N皇后问题。
    如果问题规模为 n，排列树最多有 n! 个叶子节点。

3. 剪枝函数

回溯法不是完全暴力搜索，它会在搜索过程中使用剪枝函数去掉不可能产生解的子树。

剪枝函数分为两类：

  • 约束函数：剪掉不满足约束条件的子树。
    例如：N皇后中，当前放置位置会与已有皇后冲突，就不继续搜索。
  • 限界函数：剪掉不可能得到最优解的子树。
    例如：0/1背包中，即使把剩余所有物品都装进去，总价值也无法超过当前最优值，就剪掉。

二、回溯法的核心三要素

使用回溯法时，通常围绕三个量展开：

  1. 路径：已经做出的选择。
  2. 选择列表：当前还可以做出的选择。
  3. 结束条件：到达解空间树底部，或者已经找到一个可行解，无法再继续选择。

这三个要素对应回溯算法的递归函数结构。

三、回溯法通用模板

回溯法可以用递归实现，伪代码非常统一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
result = []                    # 保存所有可行解

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径的一份拷贝)   # 注意：不能直接保存引用
        return

    for 选择 in 选择列表:
        if 选择不合法:
            continue              # 剪枝

        做选择                      # 把选择加入路径，并更新状态
        backtrack(路径, 新的选择列表)
        撤销选择                    # 状态恢复，以便尝试其他分支

Python 风格的通用模板：

1
2
3
4
5
6
7
8
9
10
11
12
def backtrack(path, choices):
    if is_goal(path):
        result.append(path.copy())
        return

    for choice in choices:
        if not is_valid(choice, path):
            continue

        path.append(choice)        # 做选择
        backtrack(path, get_choices(choice))
        path.pop()                 # 撤销选择

要点：

  • 递归前“做选择”，递归后“撤销选择”。
  • 保存结果时要复制当前路径，例如 path.copy() 或 path[:]。
  • 剪枝条件可以放在进入递归前，以减少不必要的递归。

四、经典问题详解

1. 全排列问题

问题：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

决策思路：

  • 每次从剩余数字中选择一个加入当前排列。
  • 用一个 used 数组记录哪些数字已经被选过。
  • 当排列长度等于原数组长度时，找到一个完整排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def permute(nums):
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])   # 拷贝路径
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack()

            path.pop()               # 撤销选择
            used[i] = False          # 恢复状态

    backtrack()
    return result

如果数组中有重复元素，需要先排序，然后跳过同一层中重复的分支：

1
2
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

这样可以保证相同数字在同一层只被使用一次，避免重复排列。

2. 组合问题

问题：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

决策思路：

  • 为避免 [1,2] 和 [2,1] 这种重复，使用 start 索引，保证选择顺序递增。
  • 每次从 start 开始向后选择，下一次递归从 i + 1 开始。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def combine(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        # 剪枝：如果剩余可选数不够凑齐 k 个，就直接返回
        # i <= n - (k - len(path)) + 1
        end = n - (k - len(path)) + 1
        for i in range(start, end + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result

剪枝条件：

1
i <= n - (k - len(path)) + 1

含义是：还需要选 k - len(path) 个数，当前最多只能选到 n - (k - len(path)) + 1，否则剩余数量不够。

3. 子集问题

问题：给定一个整数数组 nums，返回其所有子集。

决策思路：

  • 每个元素有“选”和“不选”两种状态。
  • 也可以看成组合问题，长度为 0 到 n 的所有组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])    # 每个节点都是一个子集

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

如果数组中有重复元素，可以排序后：

1
2
if i > start and nums[i] == nums[i - 1]:
    continue

这样就能跳过同一层的重复元素。

4. N皇后问题

问题：在 n × n 的棋盘上放置 n 个皇后，使它们彼此不能攻击。皇后可以攻击同一行、同一列以及两条对角线上的棋子。

决策思路：

  • 逐行放置皇后。
  • 每一行中尝试所有列，检查是否与已放置的皇后冲突。
  • 用集合记录已经占用的列和对角线。

对角线表示方法：

  • 主对角线：row - col 为定值；
  • 副对角线：row + col 为定值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def solveNQueens(n):
    result = []
    board = [['.'] * n for _ in range(n)]

    cols = set()
    diag1 = set()   # 主对角线
    diag2 = set()   # 副对角线

    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return

        for col in range(n):
            d1 = row - col
            d2 = row + col

            if col in cols or d1 in diag1 or d2 in diag2:
                continue   # 冲突，剪枝

            # 做选择
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)

            backtrack(row + 1)

            # 撤销选择
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)

    backtrack(0)
    return result

时间复杂度大约为 O(n!)，但剪枝后实际运行时间会远小于这个上界。

5. 括号生成

问题：生成 n 对有效括号的所有组合。

约束条件：

  • 左括号数量不能超过 n；
  • 右括号数量不能超过左括号数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def generateParenthesis(n):
    result = []
    path = []

    def backtrack(left, right):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return

        if left < n:
            path.append('(')
            backtrack(left + 1, right)
            path.pop()

        if right < left:   # 右括号数量必须小于左括号
            path.append(')')
            backtrack(left, right + 1)
            path.pop()

    backtrack(0, 0)
    return result

6. 单词搜索

问题：给定一个 m × n 的字符网格和一个单词，判断该单词是否存在于网格中。单词必须按照字母顺序通过相邻单元格组成，同一单元格不能重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def backtrack(r, c, index):
        if index == len(word):
            return True

        if (r < 0 or r >= rows or c < 0 or c >= cols
                or visited[r][c] or board[r][c] != word[index]):
            return False

        visited[r][c] = True

        for dr, dc in directions:
            if backtrack(r + dr, c + dc, index + 1):
                return True

        visited[r][c] = False   # 回溯
        return False

    for i in range(rows):
        for j in range(cols):
            if board[i][j] == word[0]:
                if backtrack(i, j, 0):
                    return True
    return False

7. 分割回文串

问题：给定字符串 s，将其分割成一些子串，使每个子串都是回文串，返回所有可能的分割方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def partition(s):
    result = []
    path = []

    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start):
        if start == len(s):
            result.append(path[:])
            return

        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end + 1])
                backtrack(end + 1)
                path.pop()

    backtrack(0)
    return result

8. 数独求解

数独是回溯法的典型应用：在一个 9 × 9 的格子中填入数字 1~9，要求每行、每列、每个 3 × 3 宫内数字不重复。

基本步骤：

  1. 找到一个空格；
  2. 尝试填入 1~9；
  3. 如果某个数字合法，则填进去，递归处理下一个空格；
  4. 如果后续无解，则撤销当前填入，尝试下一个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solveSudoku(board):
    def is_valid(row, col, num):
        for i in range(9):
            if board[row][i] == num:
                return False
            if board[i][col] == num:
                return False
        box_row, box_col = row // 3 * 3, col // 3 * 3
        for i in range(3):
            for j in range(3):
                if board[box_row + i][box_col + j] == num:
                    return False
        return True

    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            if backtrack():
                                return True
                            board[i][j] = '.'   # 回溯
                    return False  # 1~9 都试完仍无解
        return True  # 没有空格，求解成功

    backtrack()

五、剪枝与优化技巧

剪枝是回溯法的效率关键。常用的剪枝策略有：

1. 可行性剪枝

当前选择已经无法满足约束条件时，立即停止搜索该分支。

例如：

  • N皇后中列和对角线冲突；
  • 数独中数字重复；
  • 括号生成中右括号多于左括号。

2. 最优性剪枝

在求最优解的问题中，如果当前部分解已经不可能优于已有最优解，则剪掉。

例如：

  • 0/1背包中，即使剩余物品全选也不能超过当前最优价值；
  • 旅行商问题中，当前路径长度已经大于最短路径。

3. 顺序优化

在搜索前对候选集合进行排序，优先选择限制条件多的分支，往往能减少搜索量。

例如：

  • 数独中优先填可填数字最少的空格；
  • 组合问题中先排序再去重。

4. 去重剪枝

对于有重复元素的问题，排序后在同一层递归中跳过相同元素：

1
2
if i > start and nums[i] == nums[i - 1]:
    continue

在排列问题中使用 used 数组去重：

1
2
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

5. 对称性剪枝

利用问题的对称性减少搜索空间。

例如 N皇后问题，第一行皇后只需要放在一半列上，然后通过对称得到其余解。

六、复杂度分析

回溯法的时间复杂度通常较高，一般与解空间大小有关。

1. 子集树

如果每个元素有两种选择，则解空间大小为 O(2^n)。
例如子集问题、0/1背包问题。

时间复杂度：

1
O(2^n)

2. 排列树

如果每个位置有递减的选择数量，则解空间大小为 O(n!)。
例如全排列、N皇后、旅行商问题。

时间复杂度：

1
O(n!)

3. 空间复杂度

主要取决于递归深度：

1
O(n)

其中 n 是问题规模。如果路径需要存储，空间可能为 O(n) 或更深。

由于剪枝的存在，实际运行时间可能远小于理论最坏复杂度，但最坏情况下仍然是指数级。

七、回溯法与其他算法的关系

1. 回溯法与深度优先搜索（DFS）

回溯法通常是基于 DFS 实现的。
区别在于：

  • DFS 强调遍历所有节点；
  • 回溯强调“状态重置”和“剪枝”，在搜索过程中不断尝试、撤销。

可以认为回溯法 = DFS + 剪枝 + 状态恢复。

2. 回溯法与动态规划（DP）

  • 回溯法适合搜索所有解或判断是否存在可行解；
  • 动态规划适合求最优解，并且问题具有重叠子问题和最优子结构；
  • 回溯法可以通过记忆化搜索的方式避免重复计算，接近动态规划。

例如“单词拆分”可以用回溯，也可以用动态规划。回溯+记忆化后复杂度可以接近 DP。

3. 回溯法与分支限界法

  • 回溯法是深度优先搜索，沿着一条路径一直走到底，不行再退回；
  • 分支限界法是广度优先或最小耗费优先搜索，常用于求最优解；
  • 分支限界法通常维护一个队列或优先队列，扩展节点后按某种策略选择下一个节点。

4. 回溯法与贪心算法

贪心算法每步做出局部最优选择，不回溯；
回溯法会尝试多种选择，并在不合适时撤销，因此更通用但更慢。

八、常见错误与注意事项

1. 忘记撤销选择

1
2
3
path.append(x)
backtrack(...)
# 忘记 path.pop()

会导致不同分支之间状态污染。

2. 保存结果时没有复制路径

1
result.append(path)

这样后续修改 path 时，已保存的结果也会变化。应使用：

1
result.append(path[:])

或：

1
result.append(list(path))

3. 修改全局状态后未恢复

例如使用了 visited、used、棋盘、集合等，递归返回后必须恢复到递归前的状态。

4. 剪枝条件写错

比如组合问题中 start 的更新、排列去重的条件，写错会导致漏解或重复解。

5. 递归条件不明确

一定要清楚：

  • 什么时候结束？
  • 什么时候递归？
  • 递归前后状态如何变化？

九、总结

回溯法的核心可以总结为四步：

  1. 定义解空间：明确解的结构，确定搜索树；
  2. 确定递归参数：路径、选择列表、当前状态；
  3. 编写递归函数：
    • 判断是否达到结束条件；
    • 遍历所有选择；
    • 做选择 → 递归 → 撤销选择；
  4. 加入剪枝：尽早排除不可能的分支。

回溯法适合解决的问题通常具有以下特征：

  • 需要搜索所有可行解，或任意一个可行解；
  • 解空间可以用树表示；
  • 没有多项式时间的直接算法；
  • 可以通过约束条件大幅剪枝。

掌握回溯法的核心模板后，遇到全排列、组合、子集、N皇后、数独、迷宫、括号生成、分割回文串等问题，都可以比较顺利地解决。

希望这篇博客能帮你透彻理解回溯法，并在实际编码中灵活运用。如果对某个问题有疑问，欢迎进一步交流！