12 min read2,367 words

深度优先搜索与回溯算法

简介

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的经典算法。其核心思想是“一条路走到黑”，即从起始节点出发，沿着一条分支尽可能深地探索，直到无法继续（到达叶子节点或遇到已访问节点），然后回溯到上一个分叉点，选择另一条未探索的路径继续深入。这种策略天然地使用递归或栈来实现，因为它符合“后进先出”的探索顺序。

回溯算法（Backtracking）是深度优先搜索的一种特定应用，专门用于解决在多个步骤中做出一系列选择，以寻找所有（或一个）可行解的问题。它通过系统地枚举所有可能的候选解（称为“状态空间”），并在构建候选解的过程中，一旦确定当前部分解不可能导向一个完整的有效解（即“剪枝”），就立即放弃该路径（回溯），从而避免无效的搜索。回溯算法是解决组合、排列、子集、棋盘类（如N皇后）等约束满足问题的强大工具。

理解DFS与回溯的关系至关重要：回溯 = DFS + 剪枝。普通的DFS会遍历所有节点，而回溯算法在DFS的框架上，增加了对当前路径是否“有效”或“有希望”的判断，从而提前终止对无效分支的探索，极大地提高了搜索效率。本章将深入探讨其实现框架、经典问题模型与实战应用。

核心概念

递归实现与栈模拟迭代实现

DFS最直观的实现方式是递归。递归函数隐式地利用了系统的调用栈来保存状态，代码简洁易懂。其基本模板是：访问当前节点，然后对其每一个未访问的邻接节点递归调用DFS函数。

然而，递归存在栈溢出风险（对于深度极大的树或图），且有时需要更显式的控制流程。此时，可以使用栈（Stack）来模拟递归过程，即迭代实现。我们手动维护一个栈，初始将起始节点入栈。在循环中，弹出栈顶节点并访问，然后将其所有未访问的邻接节点逆序入栈（以保证与某种递归顺序一致）。迭代实现提供了对遍历过程更精细的控制。

回溯算法通用框架

回溯算法的核心是一个递归函数，通常命名为backtrack(路径，选择列表)。它包含三个关键组成部分： 1. 路径（Path）：记录已经做出的选择，通常用一个列表（如path或track）表示当前的部分解。 2. 选择列表（Choices）：代表当前状态下可以做的所有选择。这个列表会随着路径的延伸而动态变化（例如，已使用的数字不能再被选择）。 3. 结束条件（Termination Condition）：当路径满足一个完整解的条件时（例如，长度等于原数组长度），将其记录到结果集中。

框架的关键步骤是：做出一个选择，递归进入下一层决策，然后在递归返回后“撤销选择”，将状态恢复到选择之前，以便进行下一个选择。这就是“回溯”一词的体现。

graph TD A["开始回溯"] --> B{“是否满足结束条件?”} B -- 是 --> C["记录当前路径（一个解）"] C --> D["返回/回溯"] B -- 否 --> E["遍历当前选择列表"] E --> F["做出一个选择
（更新路径与状态）"] F --> G["递归进入下一层决策
backtrack(新路径，新选择列表)"] G --> H["撤销选择
（恢复路径与状态）"] H --> E D --> I["搜索结束，返回所有解"]

三类经典回溯问题

排列问题（Permutation）：求[1,2,3]的所有排列。特征：顺序相关，[1,2]和[2,1]是不同的解。选择列表通常是所有未被使用的元素。
组合/子集问题（Combination/Subset）：求[1,2,3]的所有子集（或指定长度的组合）。特征：顺序无关，[1,2]和[2,1]被视为同一个组合。为了避免重复，我们通常引入一个start索引，保证选择是向后进行的，不会回头选之前的元素。
分割/棋盘类问题（Partition/Board）：如括号生成、分割回文串、N皇后。这类问题有更强的特定约束，需要在做出选择时进行有效性判断（剪枝），例如放置的皇后是否冲突，当前括号序列是否有效。

实战示例

示例一：全排列（Permutations）

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

def permute(nums):
"""
返回数组 nums 的所有全排列。
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []  # 存放所有结果的列表
path = []  # 当前路径（已做的选择）
used = [False] * len(nums)  # 标记数组，记录 nums 中每个元素是否已被使用
def backtrack():
# 结束条件：路径长度等于原数组长度，说明一个排列已完成
if len(path) == len(nums):
# 注意需要添加 path 的副本，因为 path 之后会被修改
res.append(path[:])
return
# 遍历当前的选择列表：所有未被使用的元素
for i in range(len(nums)):
if not used[i]:  # 如果 nums[i] 未被使用
# 做出选择
used[i] = True
path.append(nums[i])
# 递归进入下一层决策树
backtrack()
# 撤销选择（回溯）
path.pop()
used[i] = False
backtrack()
return res
# 测试代码
if __name__ == "__main__":
test_nums = [1, 2, 3]
result = permute(test_nums)
print(f"数组 {test_nums} 的全排列为：")
for perm in result:
print(perm)
print(f"共有 {len(result)} 种排列。")

示例二：子集（Subsets）

给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

def subsets(nums):
"""
返回数组 nums 的所有子集。
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
path = []
def backtrack(start):
# 关键点：每一次递归调用，当前路径都是一个子集，需要立即加入结果
res.append(path[:])
# 从 start 开始遍历，避免产生重复的子集（如 [1,2] 和 [2,1]）
for i in range(start, len(nums)):
# 做出选择
path.append(nums[i])
# 递归进入下一层，注意新的 start 是 i+1，保证元素不重复使用
backtrack(i + 1)
# 撤销选择
path.pop()
backtrack(0)
return res
# 测试代码
if __name__ == "__main__":
test_nums = [1, 2, 3]
result = subsets(test_nums)
print(f"数组 {test_nums} 的所有子集为：")
for subset in result:
print(subset)
print(f"共有 {len(result)} 个子集。")

示例三：N皇后（N-Queens）

在 N×N 的棋盘上放置 N 个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一斜线上）。返回所有不同的解决方案。

def solveNQueens(n):
"""
解决 N 皇后问题。
:type n: int
:rtype: List[List[str]]
"""
res = []
# 棋盘，初始化 n x n 的 '.' 网格
board = [['.' for _ in range(n)] for _ in range(n)]
def is_valid(row, col):
"""
检查在 board[row][col] 位置放置皇后是否有效。
"""
# 检查同一列上方是否有皇后
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上斜线（45度）是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上斜线（135度）是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
# 结束条件：所有行都成功放置了皇后
if row == n:
# 将当前棋盘转换为要求的字符串格式
temp_res = [''.join(row_list) for row_list in board]
res.append(temp_res)
return
# 遍历当前行（第 row 行）的所有列，尝试放置皇后
for col in range(n):
if is_valid(row, col):  # 剪枝：如果当前位置有效
# 做出选择
board[row][col] = 'Q'
# 递归进入下一行
backtrack(row + 1)
# 撤销选择
board[row][col] = '.'
backtrack(0)
return res
# 测试代码
if __name__ == "__main__":
n = 4
solutions = solveNQueens(n)
print(f"{n} 皇后问题的解决方案有 {len(solutions)} 种：")
for idx, solution in enumerate(solutions):
print(f"方案 {idx + 1}:")
for row in solution:
print(row)
print()  # 空行分隔不同方案

对比分析

方案	优势	劣势	适用场景
递归实现DFS/回溯	代码简洁，逻辑清晰，与算法思想高度对应；系统自动管理调用栈。	有栈溢出风险（深度过大）；调试相对复杂；对遍历流程的控制较弱。	树/图深度可预估或不大；问题逻辑适合递归描述（如回溯）；追求代码可读性。
栈模拟迭代实现DFS	无栈溢出风险；可以显式控制遍历顺序和状态；便于调试，状态在自定义栈中可见。	代码相对冗长；需要手动管理栈和访问状态；对于复杂回溯逻辑，实现可能繁琐。	树/图深度极大；需要特定遍历顺序（如逆序）；需要避免递归开销的环境。
排列类回溯	框架固定，`used`数组标记使用情况；易于理解和实现。	当元素含重复值时需要额外去重逻辑（排序+剪枝）。	求所有可能的序列，顺序重要，如全排列、字符串排列。
组合/子集类回溯	通过`start`索引避免重复，效率高；框架同样清晰。	需要理解`start`索引的含义，初学者可能混淆。	求所有可能的组合或子集，顺序不重要，如子集、组合总和。
约束类回溯（如N皇后）	通过`is_valid`函数强力剪枝，极大减少搜索空间。	有效性判断函数（剪枝条件）需要针对问题专门设计，是算法难点。	解需满足复杂约束条件，如N皇后、数独、括号生成。

最佳实践

明确路径与选择列表：在动手写代码前，先明确问题的“路径”是什么（用什么数据结构存），“选择列表”在每个步骤如何变化。这是构建回溯框架的第一步。
强化剪枝意识：在遍历选择列表时，尽早进行有效性判断（前置剪枝），而不是等到递归到底层才发现无效。例如在N皇后中，放置前就检查位置是否安全。对于包含重复元素的问题（如nums = [1,2,2]），先排序，然后在循环中添加条件if i > start and nums[i] == nums[i-1]: continue来跳过重复选择。
注意状态维护与恢复：“做出选择”和“撤销选择”必须成对出现，且要作用于完全相同的状态变量。如果选择影响了多个状态（如path和used），必须全部恢复。使用path[:]添加结果副本，避免后续操作影响已存储的结果。
从简单案例调试：使用小规模的输入（如nums=[1,2]）来手动模拟或打印递归过程，观察路径的变化，这是理解回溯流程和排查错误的最有效方法。
区分排列与组合：牢记排列问题使用used数组，组合/子集问题使用start索引。这是解决大多数相关问题的钥匙。

小结

深度优先搜索是遍历结构化数据的根本策略之一，而回溯算法是其解决组合优化问题的精妙应用。掌握“路径-选择-结束条件”的通用框架，以及“做出选择-递归-撤销选择”的核心流程，是解构众多复杂搜索问题的关键。通过排列、组合、子集以及N皇后等经典问题的练习，可以深刻体会到如何将具体问题抽象为状态空间的搜索，并利用剪枝技巧提升效率。记住，回溯的本质是暴力枚举的智能化，其威力在于系统性和可剪枝性。

下一节：广度优先搜索与层序遍历