回溯算法
回溯本质上是针对决策树的深度优先搜索（DFS）。其核心逻辑是：做出选择 -> 更新状态 -> 递归探索 -> 撤销选择（恢复状态）。在尝试下一个分支前，必须确保状态被精确还原。
def search(state):
if is_solution(state):
record(state.copy())
return
for choice in candidates(state):
if not feasible(state, choice):
continue
apply(state, choice)
search(state)
undo(state, choice)
设计要点
- 定义层级含义：明确搜索树中每一层代表什么决策步骤。
- 确定选择对象：明确当前层是在选位置、选值、选边，还是做赋值。
- 明确解与输出：清晰定义终止条件（何时算解），并处理好输出的所有权（如是否需要深拷贝）。
- 状态可逆性：每一次状态修改（Mutation）都必须有对应的精确撤销（Undo）操作，特别注意提前返回（Early Return）路径下的状态恢复。
- 剪枝安全性：仅添加那些经过证明、绝不会误删有效解的剪枝规则。
剪枝策略
- 可行性剪枝（Feasibility）：当前状态已违反约束条件，无需继续。
- 对称性剪枝（Symmetry）：等价的选择会导致重复的状态，跳过冗余分支。
- 界限剪枝（Bounds）：即使后续做出最优选择，结果也无法优于当前已知的最优解（Incumbent）。
- 记忆化（Memoization）：相同的剩余状态已求解过。此时算法开始向动态规划（DP）靠拢。
复杂度分析
- 时间复杂度：最坏情况下通常为指数级或阶乘级，因为搜索空间或输出规模本身就如此庞大。剪枝能优化实际运行时间，但通常不改变最坏情况的时间复杂度类别。
- 空间复杂度：栈深度通常与决策层数成正比（不含存储最终结果的空间）。
适用场景： 当问题需要找到一个具体解（Witness）或进行完整枚举，且约束条件能尽早排除无效的部分赋值时，回溯是首选方案。
终止与完整枚举
输入有限不自动保证终止。递归必须让某个良基度量严格减小，例如尚未赋值的位置数。搜索图而非决策树时，可能需要当前路径上的访问集合来防环。全局访问集合却可能误删不同历史到达同一顶点所产生的不同解。
上面的模板遇到解就返回，因此假设解在叶子上，或无需报告其延伸。正数子集和达到目标后可以立即返回；若允许零，继续扩展还可能产生其他合法解。同样，列表元素都是不可变整数时浅 copy() 足够，嵌套可变状态则未必。
两个二元选择的决策路径是 00,01,10,11：追加 0，递归尝试第二位的两种选择，弹出 0，再以 1 重复。每次返回后，路径必须与进入时完全一致。每个合法解都对应一条选择序列，而正确剪枝不删除任何必须保留的序列，这就证明了穷尽性。用小规模穷举基线可检查新剪枝规则。
两个具体的决策树
排列问题解释怎样选择未使用元素、恢复状态并避免重复结果。子集和按选或不选分支，并说明零与负数为什么会改变可用的剪枝规则。底层遍历方式是深度优先搜索，但回溯路径还携带自己的选择，不能仅用访问过哪些顶点概括。