约束型回溯解题框架
本节目标
用状态、约束和恢复动作，把无效选择挡在递归树之外。
前一栏先建立了枚举选择并撤销路径的基本过程。本栏继续追问：一个选择刚做出时，哪些信息已经足够证明它不合法？把这些信息作为约束随递归层同步维护，就能在进入下一层前剪去无效分支。
识别信号
- 题目要求列出全部可行方案，但每一步都有局部合法条件；
- 新选择会占用列、对角线、格子或某段字符串，后续选择不能冲突；
- 直接在叶子统一检查会产生大量必然失败的候选；
- 同一份棋盘、路径或占用集合会被多个兄弟分支复用，因此返回时必须恢复现场。
问题模型与核心不变量
把每个递归层看成一次“尚未完成的决定”。递归状态至少包含：已经做出的选择、下一步要决定的位置，以及能快速判断合法性的约束信息。
不变量是：进入递归时，共享状态准确描述当前路径；任何尚未满足的约束都不能被下一层看见。离开递归时，调用者拥有的共享状态必须和进入前完全一致。于是每一次修改都要有对称的恢复：加入路径后弹出，登记占用后删除，标记格子后写回原字符。
| 问题 | 当前层决定 | 增量约束 | 必须恢复的状态 |
|---|---|---|---|
| 分割回文串 | 下一段结束位置 | 当前子串是否回文 | 当前分割路径 |
| N 皇后 | 当前行的皇后列 | 列、主对角线、副对角线是否被占用 | 棋盘与三类占用集合 |
| 单词搜索 | 当前格继续向哪个方向走 | 字符匹配且同一路径不重复用格 | 当前格访问标记 |
通用模板
backtrack(状态):
若状态已经完成:
记录答案或报告成功
return
for 每个候选选择:
若候选违反当前约束:
continue
应用选择，并同步更新约束
backtrack(下一状态)
撤销选择，并恢复全部约束
剪枝应发生在递归调用前。这样递归树只保留仍可能通向答案的节点；它不是事后把错误答案过滤掉。恢复则不取决于最终成功或失败：只要共享状态将在兄弟分支继续使用，当前调用就必须把它交还为原状。
模板变体
- 局部可判定约束： 分割回文串无需预先保存全局表，候选区间一旦不是回文，就不递归到下一段。若字符串很长且同一段被反复判断，可进一步预处理回文表，但本题的核心仍是“只让合法切分进入递归”。
- 集合约束： N 皇后按行放置，每行天然只有一个皇后；列与两条对角线用集合表示占用。位置
(row, column)的主对角线编号为row - column，副对角线编号为row + column。 - 现场标记约束： 单词搜索中，格子只在当前路径内不可重复。把字符临时替换为标记后搜索四邻，返回前恢复原字符；不能使用永久访问集合，否则其他起点和兄弟路径会被误剪。
母题序列
按必学顺序练习：
常见误区
- 把约束放到递归叶子才检查，导致本可提前排除的分支全部展开。
- 只恢复棋盘或路径，却忘记删除列、对角线等辅助集合中的登记。
- 将单词搜索的访问标记永久保留，错误阻断另一路径。
- 把 N 皇后的对角线直接按列号记录，漏掉不同格子共享同一条对角线的冲突。
- 把“当前片段是回文”误写成“整个剩余字符串是回文”，从而错过合法的多段分割。
迁移方向
当约束可以局部验证时，回溯可用于数独、括号生成和组合构造；当状态被网格或图承载时，先判断访问是否需要恢复，再选择回溯式 DFS 或永久访问的遍历式 DFS。更强的剪枝来自更早维护的信息，但始终要先写清状态、约束与恢复三者的对应关系。