回溯与剪枝Backtracking

探索候选解，遇到不可能的分支时回退。

核心约束: 当前状态必须能够恢复到分支前。
适用问题: 约束求解、组合搜索与模式枚举。
边界与取舍: 剪枝效果高度依赖问题和探索顺序。

时间与空间#

b ≥ 2 为最大分支数，d 为搜索深度，C 为单节点检查成本；只有单分支时单独按路径长度分析。

时间成本: 未剪枝搜索树最多 $O(b^{d})$ 个节点，工作约 $O(b^{d}C)$
空间成本: 深度优先搜索状态可 $O(d)$ ，另计候选与输出

剪枝效果取决于约束和输入，不能自动改变最坏指数界。枚举 n 个元素排列有 n! 个结果，输出所有排列本身就需要 $O(n\cdot n!)$ 元素写出。

基础原理参考资料

Stanford CS106B · Recursive backtracking选择、递归探索、撤销选择的回溯模板与搜索树。