回溯与搜索树
复习
- 深度优先搜索：一路走到底再回头
- 递归：函数调用自身
- 设计递归：拆小问题、确保收敛
TL;DR
- 回溯把每个选择展开成一棵“搜索树”
- 沿一条路尝试，失败就撤销选择、回到上一步
- 它天然对应 DFS 和递归
- 回溯能求出所有解，但代价可能是指数级
正文
有些问题，需要尝试所有可能的组合，比如“列出所有排列”“摆放皇后”“选出所有子集”。暴力地试一遍所有可能，正是回溯（backtracking）擅长的领域。
把选择展开成一棵树
回溯把求解过程看成一棵搜索树：
- 树的根，是问题的起点
- 每做一次选择，就往下走一层
- 每个叶子的路径，对应一种候选方案
于是，求所有解，就变成了“遍历这棵搜索树”。这自然对应深度优先搜索：沿着一条路径深入，走到底就得到一个解（或不合法），然后退回来，换一个选择继续。
尝试，然后撤销
回溯的精髓，在“撤销”这两个字。
沿着一条路径往下走时，我们要把当前选择“记入方案”。如果这条路行不通、或者已经得到了一个完整解，就得把刚才的选择撤销，恢复到做选择之前的状态，再去试别的分支。
这个“做选择 → 深入 → 撤销 → 试下一个”的循环，天然适合用递归实现：递归调用前做选择、调用后撤销选择，调用栈自动帮我们记住每一层的位置。
它能求所有解，但可能很慢
回溯的优点很明确：只要问题能用“逐步选择”描述，它就能系统地枚举出所有解，包括那些需要复杂条件的问题。
代价则是：搜索树可能极其庞大。如果每一步都有多个选择、又没有有效的限制，节点数量会随层数指数增长，很快就搜不完。所以，回溯通常必须配合下一章的剪枝，才能在实际问题中派上用场。
思考题 1
回溯算法中，“撤销选择”为什么必不可少？
思考题 2
为什么回溯法天然适合用递归实现？
小结
知识点
- 回溯把选择过程展开成一棵搜索树
- 通过 DFS 遍历搜索树求所有解
- 核心是“做选择—深入—撤销—试下一个”
- 天然对应递归，但代价可能指数级
参考资料
- Wikipedia(zh)：回溯法：逐步尝试并回退的搜索方法
- Wikipedia(zh)：深度优先搜索：回溯遍历搜索树的基础
思考题答案（仅供参考）
思考题 1
因为回溯要在一条路径失败后，回到上一步去尝试别的分支。若不撤销之前的选择，当前方案就会被“污染”或越积越多，导致后续尝试基于错误状态进行。撤销让状态恢复干净，才能正确探索其他分支。
思考题 2
因为回溯的过程是“做选择 → 递归深入 → 撤销”，而递归调用栈天然保存了每一层的位置和状态，返回时正好对应“回到上一步”。用递归表达，逻辑与搜索树的深入、回退一一对应。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪