形式陈述

回溯把候选解空间组织成搜索树。每个节点表示一个部分解；扩展操作枚举下一步选择；可行性谓词若证明该部分解不可能延伸为完整解，就立即剪枝。一个正确回溯算法必须满足：每个输出都满足约束（可靠性），每个合法完整解对应至少一条未被错误剪去的根到叶路径（完备性）。最坏时间通常仍与搜索树节点数成正比，常为指数级；空间可通过深度优先递归控制在路径深度量级。

直觉

回溯是“试一个选择，走不通就撤销”。真正的算法价值来自部分解不变量和剪枝条件，而不是把所有组合机械枚举一遍。

例子与边界

N 皇后问题逐行放置皇后，只扩展不与已放皇后同列、同对角线的位置。数独可选约束最强的空格以减少分支。剪枝条件只能在“所有后继都不可能成功”时使用；把启发式低分误当作不可能会破坏完备性。原地修改状态时必须在返回前完全撤销，否则兄弟分支相互污染。回溯与动态规划不同：前者遍历状态树，后者在重叠子问题上缓存结果。

推论与应用

回溯用于组合生成、约束满足、解析、博弈搜索和精确指数算法；与分支限界、传播和对称性消除结合后常能显著缩小实际搜索空间。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。