大家好，我是Tony Bai。
欢迎来到我们的专栏 《AI 时代软件工程师的算法图谱》的第十四讲。
欢迎来到专栏的第五季：复杂决策与系统设计。这一季我们将挑战那些“没有捷径可走”的硬核问题。
有时候，我们面临的问题既没有明确的贪心策略，也没有简单的公式，比如：
-
数独游戏： 每一个格子的填法都依赖于其他格子的状态。 -
旅行商问题 (TSP)： 寻找经过所有城市的最短路径。 -
正则表达式： 匹配 a*b.c这样复杂的模式。
面对这些问题，最原始的方法是 暴力搜索 (Brute Force)，即穷举所有可能。而 回溯法 (Backtracking) 就是一种“有组织、有纪律”的暴力搜索。它像走迷宫一样，一条路走到黑，发现不通就退回来（回溯），换条路走。
今天，我们将深入回溯的模板，并尝试手写一个简易的 正则表达式引擎。
模式解构：试错与撤销
回溯法的本质是 DFS（深度优先搜索），但它多了一个关键步骤：状态重置（Undo / Backtrack）。
通用模板
func backtrack(path []int, choices []int) {
// 1. 终止条件 (Base Case)
if isSolution(path) {
result.add(path)
return
}
// 2. 遍历选择列表
for _, choice := range choices {
// 剪枝 (Pruning)：如果当前选择不合法，跳过
if !isValid(choice) {
continue
}
// 3. 做选择 (Do)
path.add(choice)
// 4. 递归 (Recurse)
backtrack(path, newChoices)
// 5. 撤销选择 (Undo / Backtrack) -> 核心！
path.removeLast()
}
}
分支定界 (Branch and Bound)