引言 (Introduction)
在前三篇文章中，我们从一维的数组选择（子集、排列、组合）推进到一维的切割线和二维的棋盘约束，已经积累了回溯算法的核心建模能力。本篇作为系列的收官之作，聚焦于两个最接近实际工程场景的领域：二维网格上的路径搜索与回溯 + 数据结构的组合技巧。
本文是本系列第四篇，将覆盖三道综合性的题目：单词搜索（二维网格 DFS）、IP 地址复原（纯约束剪枝）、单词搜索 II（Trie 树 + 回溯），并在结尾为整个四篇系列做出全面的复盘对照表。
1. 单词搜索（LeetCode 79）
1.1 二维网格 DFS 模式
题目：给定一个 $m \times n$ 的二维字符网格 board 和一个单词 word，判断 word 是否存在于网格中。单词必须由相邻单元格的字母构成（上下左右），同一单元格不可重复使用。
这是二维 DFS 回溯的标准模板题。相比前几篇的一维结构，二维网格引入了两个新要素：
- 方向向量：4 个移动方向。
- 原地标记：用特殊字符临时覆盖
board[i][j]来标记"已访问"，回溯时恢复。这比额外维护一个visited[m][n]二维数组更节省空间。
1.2 完整代码
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
# 方向向量：上、下、左、右
directions: List[tuple[int, int]] = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(i: int, j: int, idx: int) -> bool:
# 已匹配全部字符
if idx == len(word):
return True
# 越界检查 或 字符不匹配 或 已访问
if (i < 0 or i >= m or j < 0 or j >= n
or board[i][j] != word[idx]):
return False
# 原地标记：将当前格子覆盖为特殊字符
temp = board[i][j]
board[i][j] = '#'
# 向四个方向探索
for di, dj in directions:
if dfs(i + di, j + dj, idx + 1):
return True
# 回溯：恢复
board[i][j] = temp
return False
# 从每个格子作为起点尝试
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and dfs(i, j, 0):
return True
return False
复杂度分析：
- 时间复杂度：$O(M \cdot N \cdot 3^L)$，其中 $L$ 为
word的长度。每个位置在第一次之后有 $3$ 个可选方向（不能回头），搜索深度为 $L$，共有 $M \times N$ 个起点。 - 空间复杂度：$O(L)$，仅为递归调用栈的深度。
为什么用原地标记而不是 visited 数组？
原地标记避免了 visited = [[False]*n for _ in range(m)] 的 $O(MN)$ 空间开销，且减少了一次数组访问。在 $M, N$ 较大时，这个差异是显著的。
1.3 二维回溯的要点总结
| 要点 | 做法 |
|---|---|
| 起点枚举 | 外层循环遍历每个格子作为起点 |
| 方向遍历 | 使用 directions 向量数组统一处理 |
| 访问标记 | 原地修改（board[i][j] = '#'）+ 回溯恢复 |
| 剪枝 | 越界 / 字符不匹配 / 已访问 |
| 返回值 | dfs 返回 bool（只需一个解，链式传播） |
2. 复原 IP 地址（LeetCode 93）
2.1 问题分析
题目：给定一个只包含数字的字符串 s，通过在 s 中插入 '.' 来构造所有可能的有效 IP 地址。IP 地址由 4 个整数组成（$0$ 到 $255$），不含前导零（除非是 $0$ 本身）。
示例：s = "25525511135" → ["255.255.11.135", "255.255.111.35"]
这道题与分割回文串一脉相承——都是在一维字符串上枚举切割线。但它的约束条件更有工程气息（IP 地址的合法性），是纯约束剪枝的绝佳案例。
2.2 约束条件拆解
一个合法的 IP 段 s[start:end+1] 必须满足：
- 长度在 $1$ 到 $3$ 之间。
- 如果长度 $>1$，不能以 $0$ 开头（
"01"非法，"0"合法）。 - 整数值在 $[0, 255]$ 范围内。
2.3 完整代码
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res: List[str] = []
segments: List[str] = []
def is_valid(start: int, end: int) -> bool:
"""判断 s[start:end+1] 是否为合法 IP 段"""
# 长度检查
length = end - start + 1
if length < 1 or length > 3:
return False
# 前导零检查
if length > 1 and s[start] == '0':
return False
# 值范围检查
val = int(s[start:end + 1])
return 0 <= val <= 255
def dfs(start: int) -> None:
# 已经找到 4 段，且用完所有字符
if len(segments) == 4:
if start == len(s):
res.append('.'.join(segments))
return
# 如果剩余字符数过多（即使每段 3 个字符也放不下）或过少（每段 1 个都不够）
remaining_len = len(s) - start
remaining_segments = 4 - len(segments)
if remaining_len > remaining_segments * 3 or remaining_len < remaining_segments:
return # 纵向剪枝：长度不可能
# 每段最多 3 个字符
for end in range(start, min(start + 3, len(s))):
if is_valid(start, end):
segments.append(s[start:end + 1])
dfs(end + 1)
segments.pop()
dfs(0)
return res
纵向剪枝的精妙之处：
remaining_len > remaining_segments * 3 # 剩余字符太多，每段 3 个都放不下
remaining_len < remaining_segments # 剩余字符太少，每段至少 1 个都不够
这两行代码精确划定了"剩余字符数"的可行区间：
$$ \text{remaining\_segments} \leq \text{remaining\_len} \leq \text{remaining\_segments} \times 3 $$任何不在此区间的状态都不可能填完剩下的 IP 段，可以直接剪枝。这是典型的"基于剩余容量的纵向剪枝"，与组合问题中的 i <= n - need + 1 逻辑同源。
3. 单词搜索 II（LeetCode 212）
3.1 问题分析
题目：给定一个二维网格 board 和一个单词列表 words，找出所有在网格中出现的单词。
如果对每个单词单独做一次 79 题的 DFS，时间复杂度将是 $O(M \cdot N \cdot 3^L \cdot K)$（$K$ 为单词数），在 $K$ 较大时不可接受。这道题需要引入Trie 树（前缀树）来将多个单词的搜索合并为一次 DFS：
- 将所有
words构建成一棵 Trie。 - DFS 遍历网格时，同时跟踪当前路径在 Trie 中的节点。
- 如果当前节点是某个单词的结尾，记录该单词。
- 如果当前前缀在 Trie 中不存在，直接剪枝。
核心优势：Trie 将所有单词的搜索合并，DFS 只需执行一次网格遍历，时间复杂度从 $O(K \cdot M \cdot N \cdot 3^L)$ 降至 $O(M \cdot N \cdot 3^L)$（$L$ 为最长单词长度）。
3.2 Trie 节点定义
from typing import List, Optional
class TrieNode:
"""Trie 树节点"""
def __init__(self) -> None:
self.children: dict[str, TrieNode] = {}
self.word: Optional[str] = None # 若不为 None，表示该节点是一个单词的结尾
与标准 Trie 不同，这里我们在叶节点直接存储完整的单词字符串，而不是布尔标记。这样在回溯过程中发现单词时可以直接添加到结果集。
3.3 完整代码
from typing import List, Optional
class TrieNode:
def __init__(self) -> None:
self.children: dict[str, TrieNode] = {}
self.word: Optional[str] = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# 1. 构建 Trie
root = TrieNode()
for w in words:
node = root
for ch in w:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = w # 在末尾存储完整单词
m, n = len(board), len(board[0])
res: List[str] = []
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(i: int, j: int, node: TrieNode) -> None:
ch = board[i][j]
if ch not in node.children: # 前缀不在 Trie 中，剪枝
return
next_node = node.children[ch]
# 检查是否匹配到完整单词
if next_node.word is not None:
res.append(next_node.word)
next_node.word = None # 去重：每个单词只记录一次
# 原地标记已访问
board[i][j] = '#'
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
# 回溯：恢复
board[i][j] = ch
# 优化：如果当前节点已经没有孩子了，从父节点删除它（剪枝 Trie）
if not next_node.children:
del node.children[ch]
# 2. 从每个格子开始 DFS
for i in range(m):
for j in range(n):
dfs(i, j, root)
return res
3.4 设计要点
next_node.word = None 的去重机制：
当一个单词被找到后，将 Trie 节点中的 word 字段置空，避免后续路径再次匹配到相同的单词。这比使用 set 去重更优雅——去重逻辑内嵌在 Trie 中，不需要额外的数据结构。
Trie 的渐进式剪枝（del node.children[ch]）：
if not next_node.children:
del node.children[ch]
当一个 Trie 节点的所有子节点都被删除了（意味着以该节点为前缀的所有单词都已被找到），该节点本身也不再有用。从父节点删除它可以缩小后续搜索的 Trie 规模——这是 Trie 配合回溯的经典"用后即焚"优化。
复杂度：
- 时间复杂度：$O(M \cdot N \cdot 3^L)$，其中 $L$ 为 Trie 树深度。每个格子至多探索一次，Trie 剪枝使得大部分路径提前终止。
- 空间复杂度：$O(K \cdot L)$ 用于 Trie 存储 + $O(L)$ 递归栈。
4. 全系列复盘对照表
本系列四篇文章覆盖了回溯算法的完整知识体系。下表汇总了每一篇的核心内容、关键技巧和配套题目，方便读者索引与复习：
| 篇目 | 主题 | 核心框架 | 关键技巧 | 配套题目 |
|---|---|---|---|---|
| 第一篇 | 回溯框架与子集问题 | path + start + pop() 模板 |
决策树视角、横向剪枝（i > start）、复杂度 $O(N \cdot 2^N)$ |
LC 78, 90, 1863 |
| 第二篇 | 排列与组合 | start 的有无决定"顺序是否被考虑" |
排列去重（not used[i-1]）、纵向剪枝（remaining < cand、n - need + 1） |
LC 46, 47, 77, 39, 40 |
| 第三篇 | 分割与棋盘问题 | 切割线建模、行列-对角-宫约束哈希 | 回文 DP 预处理、对角线数学建模（row ± col）、九宫格索引、MRV 启发式 |
LC 131, 51, 37 |
| 第四篇 | 网格搜索与高级技巧 | 二维方向向量 + 原地标记 | Trie + 回溯合并搜索、渐进式剪枝、容量约束剪枝 | LC 79, 93, 212 |
4.1 回溯算法的统一思维框架
贯穿整个系列的，是一套从问题建模到代码实现的统一思维流程：
第零步：判断是否适合回溯。 如果问题要求"所有可能的……"（枚举类）且解空间呈组合爆炸特征，回溯几乎总是正确的方法。
第一步：定义状态（path 是什么？）。
这是最重要也是最容易出错的环节。状态的定义直接决定了递归树的结构：
- 子集/组合/排列：
path= 已选元素的列表 - 分割问题：
start= 切割线的位置 - 棋盘问题：
board[row] = col或board[i][j] = d - 网格问题：
(i, j, idx)或(i, j, trie_node)
第二步：确定递归层级与递进方式。 一行递进？一个元素递进？一个空格递进？切割线后移？方向向量移动？
第三步：设计约束建模。 将"非法状态"的判断从 $O(N)$ 降到 $O(1)$——集合、布尔数组、位运算、Trie 节点查找。
第四步：添加剪枝。 纵向剪枝（基于剩余容量/长度/和值）和横向剪枝（去重）是回溯从"能跑"到"能过题"的关键。
第五步：决定返回类型。
void（枚举所有解）vs bool（找到一个解就停止）。
4.2 回溯与动态规划的分界线
许多读者会困惑：什么情况用回溯，什么情况用动态规划？
| 维度 | 回溯 | 动态规划 |
|---|---|---|
| 问题特征 | 枚举所有解/一条路径 | 求最优值/计数 |
| 状态空间 | 指数级（必须遍历） | 多项式级（有重叠子问题） |
| 典型问法 | “返回所有可能的……” | “最多/最少/最长……” |
| 复杂度 | 输出-sensitive（指数级） | $O(N)$ 或 $O(N^2)$ |
一句粗糙但实用的判断：“看到 ‘所有’ 想回溯，看到 ‘最优’ 想 DP。”
但两者并非互斥——有些题目（如分割回文串的"最少切割次数"变体）需要回溯 + DP 的组合。此时 DP 负责"求值"，回溯负责"收集路径"。这是一种常见的混合命题模式。
结论 (Conclusion)
回溯算法是算法竞赛和面试中占比最大的板块之一。从子集到排列，从组合到棋盘，从一维到二维，从纯回溯到 Trie+回溯——所有变体都凝聚在同一个核心框架上：
def dfs(state):
if 满足终止条件:
记录结果; return
for choice in 当前状态的可选集合:
if 剪枝条件(choice): continue
做选择(choice); 更新状态
dfs(next_state)
撤销选择(choice); 恢复状态 # ← 回溯的灵魂
这不是一段需要死记硬背的代码，而是对"试探—撤回—重试"这一基本问题求解策略的形式化表达。一旦你在决策树的层次上理解了 start 参数的语义、剪枝条件的分类（横向 vs 纵向）、状态标记的建模方式（集合 vs 数组 vs 原地），你就真正掌握了回溯算法。
本系列到此完结。 推荐配套练习顺序：
- 先独立重做每篇文章标注的 LeetCode 题目。
- 尝试将每篇文章的核心框架用自己的话重新写一版代码。
- 遇到新题时，按 4.1 节的五步思维流程建模——而不是着急查题解。
当你发现自己不再需要记回溯模板，而是在脑子里自动浮现出决策树的形状时，就是功成之时。