---

新手必看：回溯算法快速入门

算法是编程的灵魂，而回溯算法（Backtracking Algorithm）是解决很多计算机科学问题，特别是搜索和优化问题的强大工具。对于刚踏入算法大门的你来说，回溯算法可能听起来有点神秘，但掌握了它的核心思想，你会发现它其实是一种非常直观且优雅的解题方法。

本文将带你深入了解回溯算法，从它的基本概念到实际应用，一步步拆解，让你快速掌握并能在解决问题时游刃有余。

第一章：算法，为什么需要回溯？

在计算机科学中，我们经常需要解决这样一类问题：从众多的可能性中找到一个或所有的解。比如，在棋盘上放棋子，要满足某些规则；或者从一堆数字中选出一些，让它们的和等于某个目标值；再或者，找到迷宫的一条出路。

这类问题的共同点是：
1. 问题的解可以分解为一系列的决策步骤。
2. 每一步决策都会影响后续可能的决策。
3. 我们需要探索不同的决策组合，直到找到满足条件的解。

最简单粗暴的方法是“暴力搜索”或“穷举法”，也就是尝试所有的可能性。但这往往会导致计算量呈指数级增长，效率极其低下，甚至在问题规模稍大时就无法计算。

有没有一种更聪明的方法？既能系统地探索所有可能性，又能及时发现无效的路径，避免做无用功？

答案就是——回溯算法。

回溯算法的核心思想是：沿着一条路径向下探索，如果在当前路径上发现无法达到目标（不满足约束条件），就“退回”到上一步，尝试其他的路径。 就像在走迷宫，走到死胡同就退回来，尝试另一条岔路。

第二章：理解回溯的核心概念

回溯算法本质上是一种深度优先搜索（DFS）的变体，它在搜索过程中动态地构建问题的解空间树（或称为决策树）。

要理解回溯，需要把握几个关键概念：

1. 状态（State）/ 路径（Path）：在回溯搜索的每一步，我们都处于一个特定的“状态”或已经构建了一部分的“路径”。这个状态/路径记录了我们到目前为止所做的决策。
2. 选择列表（Choice List）：在当前状态下，我们有哪些合法的下一步“选择”。
3. 约束条件（Constraints）：哪些选择是合法的？什么时候当前路径是无效的？这些由问题的约束条件决定。
4. 目标状态（Goal State）/ 基本情况（Base Case）：什么时候我们找到了一个完整的解？什么时候当前路径无法再向下探索（达到搜索树的叶子节点或发现无效路径）？这些是递归的终止条件。
5. 回溯（Backtrack）：这是回溯算法的精髓。当我们在当前路径上无法继续（走到死胡同）或者完成了一个分支的探索后，需要撤销上一步的决策，回到之前的状态，尝试列表中的其他选择。

可以想象一个决策树：

• 根节点代表问题的初始状态。
• 从一个节点出发的每条边代表一个可能的选择。
• 每个节点代表做出一系列选择后的状态。
• 树的路径代表一系列的决策序列。
• 叶子节点代表达到目标状态或无法继续探索的状态。

回溯算法就是在这样一棵决策树上进行深度优先搜索，当发现当前路径不可行时，就“回溯”到父节点，尝试同一父节点的其他子节点（其他选择）。

第三章：回溯算法的基本框架

回溯算法通常使用递归来实现。一个典型的回溯函数通常会接收当前的“状态”或“路径”作为参数，并在函数体内部进行如下操作：

“`
函数 backtrack(路径/状态):
# 1. 检查是否达到目标状态 (递归的终止条件)
如果 路径/状态 满足找到一个解的条件:
将当前 路径/状态 记录为一个解
# 可以选择返回（如果只需要一个解）或继续（如果需要所有解）
return

# 2. 剪枝 (可选，优化搜索)
如果 路径/状态 已经不满足约束条件，不可能达到目标:
    return # 提前终止当前分支的搜索

# 3. 探索所有可能的选择
遍历 当前状态下 所有可能的选择:
    # a. 做出选择 (更新状态/路径)
    选择 i 加入到 路径/状态 中

    # b. 递归探索 (进入下一层决策)
    backtrack(新的 路径/状态)

    # c. 撤销选择 (回溯)
    从 路径/状态 中移除 选择 i
    # 恢复到做出选择 i 之前的状态，以便尝试下一个选择

“`

这个框架中的“做出选择 -> 递归探索 -> 撤销选择”三步是回溯算法的核心循环，特别是“撤销选择”这一步，它保证了在探索完一个分支后，能够恢复现场，去探索其他分支。

第四章：回溯算法经典案例分析

理论结合实践才能更好地理解。我们来分析几个经典的回溯问题。

案例一：全排列问题 (Permutations)

问题描述: 给定一个不含重复数字的序列，返回其所有可能的全排列。
例如：输入 [1, 2, 3]，输出 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。

分析:
* 决策步骤: 每次从剩余的数字中选择一个放在当前排列的末尾。
* 状态/路径: 当前已经构建的排列（例如 [1, 2]）。
* 选择列表: 还没被使用的数字。
* 约束条件: 不能重复使用数字。
* 目标状态: 当排列的长度等于原始序列的长度时，就找到了一个完整的排列。

回溯过程:

1. 初始状态：空路径 []，所有数字 [1, 2, 3] 都是可选的。
2. 选择 1: 将 1 加入路径，路径变为 [1]。可选数字变为 [2, 3]。
   • 进入下一层递归 backtrack([1], [2, 3])。
   • 在路径 [1] 的基础上，选择 2: 将 2 加入路径，路径变为 [1, 2]。可选数字变为 [3]。
     • 进入下一层递归 backtrack([1, 2], [3])。
     • 在路径 [1, 2] 的基础上，选择 3: 将 3 加入路径，路径变为 [1, 2, 3]。可选数字变为 []。
       • 路径长度达到 3，找到一个解 [1, 2, 3]，记录。
       • 撤销选择 3: 从路径 [1, 2, 3] 移除 3，路径变回 [1, 2]。
     • 在路径 [1, 2] 的基础上，没有其他可选数字了。
     • 撤销选择 2: 从路径 [1, 2] 移除 2，路径变回 [1]。可选数字变回 [2, 3]。
   • 在路径 [1] 的基础上，选择 3: 将 3 加入路径，路径变为 [1, 3]。可选数字变为 [2]。
     • 进入下一层递归 backtrack([1, 3], [2])。
     • 在路径 [1, 3] 的基础上，选择 2: 将 2 加入路径，路径变为 [1, 3, 2]。可选数字变为 []。
       • 路径长度达到 3，找到一个解 [1, 3, 2]，记录。
       • 撤销选择 2: 从路径 [1, 3, 2] 移除 2，路径变回 [1, 3]。
     • 在路径 [1, 3] 的基础上，没有其他可选数字了。
     • 撤销选择 3: 从路径 [1, 3] 移除 3，路径变回 [1]。可选数字变回 [2, 3]。
   • 在路径 [1] 的基础上，没有其他可选数字了。
   • 撤销选择 1: 从路径 [1] 移除 1，路径变回 []。可选数字变回 [1, 2, 3]。
3. 选择 2: 将 2 加入路径，路径变为 [2]。可选数字变为 [1, 3]。
   • … (类似上述过程，探索以 2 开头的排列)
4. 选择 3: 将 3 加入路径，路径变为 [3]。可选数字变为 [1, 2]。
   • … (类似上述过程，探索以 3 开头的排列)

直到所有分支都探索完毕。

代码实现 (Python 示例):

“`python
def permute(nums):
results = []
n = len(nums)
used = [False] * n # 标记数字是否已经被使用过

def backtrack(path):
    # 1. 达到目标状态
    if len(path) == n:
        results.append(list(path)) # 记录找到的一个解
        return

    # 2. 探索所有可能的选择
    for i in range(n):
        # 3. 约束条件: 剪枝 - 如果当前数字已经被使用，则跳过
        if used[i]:
            continue

        # a. 做出选择
        path.append(nums[i])
        used[i] = True # 标记为已使用

        # b. 递归探索
        backtrack(path)

        # c. 撤销选择 (回溯)
        path.pop()
        used[i] = False # 恢复标记，以便其他分支使用这个数字

backtrack([]) # 从空路径开始
return results

示例调用

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

在这个例子中，path 代表当前排列，used 数组帮助我们判断哪些数字是当前可以选择的。回溯的核心体现在 path.pop() 和 used[i] = False 这两行，它们撤销了最近一次的选择，恢复了之前的状态。

案例二：N 皇后问题 (N-Queens)

问题描述: 在 N×N 的国际象棋棋盘上放置 N 个皇后，使得任意两个皇后都不能互相攻击。一个皇后可以攻击同一行、同一列或同一斜线上的其他皇后。返回所有有效的放置方案。

分析:
* 决策步骤: 逐行放置皇后。在第 k 行选择一个合法的列放置第 k 个皇后。
* 状态/路径: 一个列表或数组，记录了前 k 行皇后所在的列位置。例如 [1, 3, 0, 2] 表示在 4×4 棋盘上，第一行皇后在第 1 列，第二行在第 3 列，第三行在第 0 列，第四行在第 2 列。
* 选择列表: 在当前行，哪些列可以放置皇后？这取决于前面已经放置的皇后。
* 约束条件: 新放置的皇后不能与之前已放置的任何皇后同列、同主对角线、同副对角线。
* 同列：新皇后的列不能与已有皇后的列相同。
* 同主对角线：如果两个皇后分别在 (r1, c1) 和 (r2, c2)，且 r1 - c1 == r2 - c2，则它们在同一主对角线上。
* 同副对角线：如果两个皇后分别在 (r1, c1) 和 (r2, c2)，且 r1 + c1 == r2 + c2，则它们在同一副对角线上。
* 目标状态: 成功放置了 N 个皇后（即在 N 行都放置了皇后）。

回溯过程 (以 N=4 为例):

1. 初始状态：空棋盘，准备放置第 0 行的皇后。

2. 在第 0 行，尝试在第 0 列放置皇后：棋盘状态 (简化表示) [[Q, ., ., .]]。路径 [0]。

   • 进入下一层，放置第 1 行的皇后。
   • 在第 1 行，尝试第 0 列？不行，与第 0 行的皇后同列。
   • 在第 1 行，尝试第 1 列？不行，与第 0 行的皇后同主对角线 (0-0 == 1-1)。
   • 在第 1 行，尝试第 2 列？可行。棋盘 [[Q, ., ., .], [., ., Q, .]]。路径 [0, 2]。
     • 进入下一层，放置第 2 行的皇后。
     • 在第 2 行，尝试第 0 列？不行 (与第 0 行同副对角线 0+0 == 2+0)。
     • 在第 2 行，尝试第 1 列？不行 (与第 1 行同主对角线 1-2 != 2-1; 1+2 != 2+1; 检查与第 0 行：0-0 != 2-1; 0+0 != 2+1)。哦等等，需要实现一个 isValid 函数来检查。

   让我们重新组织一下，重点放在 isValid 检查和回溯。

   isValid(row, col, board) 函数：检查在 board 棋盘的前 row 行已经放置了皇后，现在尝试在第 row 行的 col 列放置新皇后是否合法。
   * 遍历前面的行 i 从 0 到 row-1：
   * 检查是否同列：board[i] == col
   * 检查是否同主对角线：row - col == i - board[i]
   * 检查是否同副对角线：row + col == i + board[i]
   * 如果任一条件为真，则 isValid 返回 False。
   * 如果遍历完所有前面的行都没有冲突，则 isValid 返回 True。

   backtrack(row, board) 函数：尝试在第 row 行放置皇后。
   * 基本情况: 如果 row == n (已经成功放置了 N 行皇后)，则找到一个解，将 board 转换为所需的格式并添加到结果集，返回。
   * 探索选择: 遍历当前行的所有列 col 从 0 到 n-1。
   * 约束检查/剪枝: 如果 isValid(row, col, board) 为真（可以在当前列放置皇后）：
   * 做出选择: 在 board[row] 记录皇后放置的列 col (例如 board[row] = col)。
   * 递归探索: 调用 backtrack(row + 1, board) 尝试放置下一行的皇后。
   * 撤销选择 (回溯): 将 board[row] 重置为一个标记（例如 -1 或其他表示无皇后的值），恢复现场，以便在当前行尝试下一列。

代码实现 (Python 示例概念):

“`python
def solveNQueens(n):
results = []
# board 用一个列表表示，board[i] 表示第 i 行皇后所在的列
# 初始化为 -1 或其他标记，表示该行还没放皇后
board = [-1] * n

def is_valid(row, col, board):
    # 检查当前位置 (row, col) 是否合法，不与之前行 (0 到 row-1) 的皇后冲突
    for i in range(row):
        # 同列: board[i] == col
        # 同主对角线: 行差等于列差 |row - i| == |col - board[i]| => row - i == col - board[i] 或 row - i == -(col - board[i])
        # 同副对角线: 行差等于列差的相反数 |row - i| == -|col - board[i]| => row - i == -(col - board[i]) 或 row - i == (col - board[i])
        # 更简单的对角线判断: row - col == i - board[i] (主对角线) 或 row + col == i + board[i] (副对角线)
        if board[i] == col or \
           row - col == i - board[i] or \
           row + col == i + board[i]:
            return False
    return True

def backtrack(row, board):
    # 1. 达到目标状态
    if row == n:
        # 找到一个解，将 board 转换为题目要求的格式 (例如 "." 和 "Q" 的字符串列表)
        solution = ["." * n for _ in range(n)]
        for r in range(n):
            solution[r] = solution[r][:board[r]] + "Q" + solution[r][board[r]+1:]
        results.append(solution)
        return

    # 2. 探索所有可能的选择 (遍历当前行的所有列)
    for col in range(n):
        # 3. 约束条件检查
        if is_valid(row, col, board):
            # a. 做出选择
            board[row] = col

            # b. 递归探索下一行
            backtrack(row + 1, board)

            # c. 撤销选择 (回溯)
            board[row] = -1 # 恢复当前行的状态

backtrack(0, board) # 从第 0 行开始放置
return results

示例调用

print(solveNQueens(4))
“`

N 皇后问题很好地展示了如何利用约束条件进行剪枝，避免探索无效的分支。is_valid 函数就是剪枝的关键。

案例三：子集问题 (Subsets)

问题描述: 给定一个不含重复数字的整数数组 nums，返回该数组所有可能的子集（幂集）。

分析:
* 决策步骤: 对于数组中的每一个数字，我们可以选择“包含”它在当前子集中，或者“不包含”它。
* 状态/路径: 当前已经构建的子集。
* 选择列表: 考虑下一个数字是“包含”还是“不包含”。
* 约束条件: 无（对于不含重复数字的情况）。
* 目标状态: 考虑完了所有的数字。

回溯过程:

对于数字 nums[i]，有两种选择：
1. 将 nums[i] 添加到当前子集，然后考虑 nums[i+1]。
2. 不将 nums[i] 添加到当前子集，直接考虑 nums[i+1]。

这是一个基于选择当前元素还是跳过当前元素的决策模型。

backtrack(index, path) 函数：考虑从索引 index 开始的数字，构建子集，当前子集是 path。

1. 基本情况: 当 index == len(nums) 时，表示所有数字都考虑完了，将当前的 path 作为一个完整的子集添加到结果集。
2. 探索选择:
   • 选择 1: 包含 nums[index]
     • 做出选择: 将 nums[index] 加入 path。
     • 递归探索: 调用 backtrack(index + 1, path) 考虑下一个数字。
     • 撤销选择 (回溯): 从 path 移除 nums[index]。
   • 选择 2: 不包含 nums[index]
     • 做出选择: 不做任何改变，path 保持原样。
     • 递归探索: 调用 backtrack(index + 1, path) 直接考虑下一个数字。
     • 撤销选择 (回溯): 无需撤销，因为没有做出改变。

代码实现 (Python 示例):

“`python
def subsets(nums):
results = []

def backtrack(index, path):
    # 1. 达到目标状态 (所有数字都已考虑)
    # 注意：子集问题的基本情况是处理完所有元素后，
    # 但在回溯过程中，任意时刻的 path 都是一个有效的子集，所以每进入一层都可以记录
    results.append(list(path)) # 记录当前的 path 作为找到的一个子集

    # 如果所有数字都已考虑，结束当前分支 (虽然上面已经记录了，但这里是为了防止越界)
    if index == len(nums):
         return

    # 2. 探索所有可能的选择 (从当前索引开始，考虑后面的数字)
    # 这里和排列问题有点不同，排列是每次从剩余元素中选一个
    # 子集问题是对于每个元素，都有“选”或“不选”两种情况，
    # 或者理解为：当前子集 path 已经确定了前面的一些元素，现在从 index 开始往后选元素加入
    # 因此，对于当前这一层递归，应该从 index 开始向后遍历
    for i in range(index, len(nums)):
        # a. 做出选择：包含 nums[i]
        path.append(nums[i])

        # b. 递归探索：考虑下一个元素是 i+1 (因为 nums[i] 已经选择了)
        backtrack(i + 1, path)

        # c. 撤销选择 (回溯)：移除 nums[i]，尝试不包含 nums[i] 的情况
        path.pop()

# 另一种更直观的实现方式，直接体现“选”或“不选”：
def backtrack_v2(index, path):
    # 1. 达到目标状态 (所有数字都已考虑)
    if index == len(nums):
        results.append(list(path))
        return

    # 2. 探索选择
    # 选择 1: 不包含 nums[index]
    backtrack_v2(index + 1, path) # 直接跳过当前数字

    # 选择 2: 包含 nums[index]
    path.append(nums[index]) # 做选择
    backtrack_v2(index + 1, path) # 递归探索
    path.pop() # 撤销选择 (回溯)

# 使用第一种实现方式，从索引 0 开始，空路径
# backtrack(0, [])

# 使用第二种更清晰的实现方式
backtrack_v2(0, [])

return results

示例调用

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

输出: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] (顺序可能不同)

``
注意在子集问题中，backtrack_v2函数的结构更清晰地体现了每个元素的“选”与“不选”两个分支。而第一个backtrack函数的实现，其循环for i in range(index, len(nums))暗含了从当前index开始，依次考虑将后面的每个元素作为当前分支的起点加入路径，从而生成所有子集。这两种写法都是回溯，只是构建决策树的方式略有不同。对于初学者，backtrack_v2` 可能更容易理解“选”与“不选”的二叉树结构。

第五章：回溯算法的优化与剪枝

回溯算法的时间复杂度通常是指数级的，因为它需要探索决策树的很多分支。然而，通过剪枝（Pruning）可以显著提高效率。剪枝就是在搜索过程中，一旦发现当前路径不可能导向有效的解，就立即停止在该路径上的进一步搜索，退回尝试其他路径。

N 皇后问题中的 is_valid 函数就是一种剪枝：如果在某个位置放皇后会与之前的皇后冲突，我们就不在该位置放置，从而避免了探索所有基于这个无效选择的后续分支。

其他的剪枝技巧包括：
* 基于边界条件的剪枝: 例如，在组合问题中，如果已经选择的元素数量加上剩余元素的数量小于目标数量，就可以剪枝。
* 基于排序的剪枝: 如果输入数据有序，可以利用这个特性避免生成重复的组合或排列，或者在搜索时跳过一些不可能的分支。在解决包含重复数字的全排列或组合问题时，通常需要先对数组排序，并在回溯时增加判断条件来跳过重复的元素。
* 状态压缩: 在某些问题中，可以使用位运算等方式压缩状态表示，加快判断速度。

第六章：识别和应用回溯算法

如何判断一个问题可以使用回溯算法？

通常，如果一个问题需要你寻找所有可能的解或者判断是否存在一个解，并且问题的解可以分解为一系列有约束条件的决策步骤，那么回溯算法很可能适用。

常见的可以应用回溯算法的问题类型：

• 组合问题: 从一组元素中选择 k 个元素的所有组合。
• 排列问题: 从一组元素中生成所有可能的排列。
• 子集问题: 生成一个集合的所有子集。
• 棋盘问题: 如 N 皇后、数独求解、迷宫寻路等。
• 分割问题: 如字符串分割成满足条件的子串。
• 组合总和问题: 找到一组数字的所有组合，使其和等于一个目标值。
• 其他约束满足问题 (CSP)。

当你遇到这类问题时，可以按照以下步骤思考：

1. 定义“路径”或“状态”： 用什么数据结构来记录当前的决策序列？（例如：一个列表、一个数组、一个棋盘状态等）
2. 定义“选择列表”： 在当前状态下，有哪些可能的下一步决策？（例如：从剩余的数字中选择一个、在当前行的某一列放置皇后、选择包含或不包含当前元素等）
3. 定义“约束条件”： 哪些选择是合法的？什么时候当前路径是无效的？如何检查？
4. 定义“目标状态”或“基本情况”： 什么时候找到了一个完整的解？什么时候递归应该终止？
5. 设计回溯函数： 参数通常包括当前的状态/路径和可能需要的一些辅助信息（如索引、剩余选择等）。在函数内部实现“做出选择 -> 递归探索 -> 撤销选择”的逻辑。

第七章：学习回溯的常见误区与建议

常见误区：

• 忘记“撤销选择”： 这是最容易犯的错误。如果不在递归调用返回后撤销所做的选择，当前状态就不会恢复，后续分支的探索就会受到影响，导致结果错误。
• 基本情况定义不准确： 导致漏解或重复解，或者无限递归。
• 约束条件判断错误： 导致生成无效的解或漏掉有效的解。
• 处理重复元素的问题： 如果输入中包含重复元素，需要额外的逻辑（如先排序，然后跳过相邻的相同元素）来避免生成重复的解。

学习建议：

1. 从简单问题入手： 先从全排列、组合、子集等基础问题开始练习。
2. 手绘决策树： 对于小规模的输入，尝试手绘决策树，模拟回溯过程，加深理解。
3. 理解递归过程： 回溯是递归的经典应用。确保你理解递归的调用栈、参数传递和返回值。
4. 模板化思考： 掌握回溯的基本框架（选择、递归、撤销），遇到新问题时往这个框架上套。
5. 重点理解“撤销选择”的作用： 思考如果不撤销会发生什么。
6. 多练习： 在 LeetCode、LintCode 等平台上找到回溯相关的题目（通常在“回溯”、“组合”、“排列”、“子集”等标签下）进行练习。从易到难。
7. 关注剪枝技巧： 在掌握基本回溯后，学习如何通过剪枝优化算法效率。

第八章：总结与展望

回溯算法是一种通用的搜索算法，适用于解决许多组合优化和约束满足问题。它通过递归和状态的维护，系统地探索解空间，并在遇到无效路径时进行“回退”。

掌握回溯算法，你不仅能解决一类特定的问题，更能提升你对递归、深度优先搜索和问题分解的理解。它也是很多更高级算法（如图论中的一些搜索算法）的基础。

回溯算法的时间复杂度通常较高，但通过有效的剪枝可以大幅提升性能。理解问题的约束条件并将其转化为剪枝逻辑是提高回溯算法效率的关键。

从现在开始，拿起笔和纸，或者打开你的代码编辑器，选择一个简单的回溯问题，尝试用我们介绍的框架去解决它。一步步理解“做出选择”、“递归探索”、“撤销选择”的过程。相信通过练习，你一定能快速掌握回溯算法这个强大的工具！

祝你在算法学习的道路上越走越远！

---