搜索与剪枝综合解题框架
本节目标
从状态空间、目标类型和重复结构出发，为综合搜索选择剪枝与辅助结构。
搜索题真正困难的地方，通常不是写出 DFS 或 BFS，而是认清“正在搜索什么”。同一份代码骨架，可能在单词之间寻找最短路，也可能在数独棋盘上恢复一个可行解；若状态、目标和重复来源没有先定义清楚，剪枝就容易变成零散技巧。
本节把综合搜索统一成五个问题：状态是什么、目标是什么、什么分支一定不可能、哪些选择彼此等价、是否需要辅助结构共享工作。
识别信号
- 每一步都能生成若干下一状态，需要求最少步数或判断能否到达；
- 约束互相影响，填入一个选择后会立即排除许多后续选择；
- 物品要分配到若干等价容器，直接枚举会反复尝试对称方案；
- 大量候选词共享前缀，逐个搜索会重复走过相同网格路径；
- 基础 DFS、BFS 或回溯已经能解题，但搜索树仍有明显的重复分支。
问题模型与核心不变量
先把状态写成足以决定后续选择的最小信息。
- 单词接龙的状态是当前单词；每条边表示修改一个字符，BFS 层数就是序列长度。
- 解数独的状态是当前棋盘以及行、列、宫已经使用的数字；三类约束必须与棋盘同步修改和撤销。
- 等和子集划分的状态是下一个待放数字和各桶当前和；每个数字恰好进入一个桶。
- 单词搜索 II 的状态是网格位置、当前 Trie 节点和本条路径已经占用的格子；Trie 路径就是仍可能匹配的单词前缀。
无论状态形式如何，访问标记和辅助信息都必须与其语义一致：BFS 在入队时标记，回溯在返回上一层前恢复，命中单词后只清除终止信息而不破坏仍可能服务其他单词的前缀路径。
通用模板
明确状态与一次转移
选择目标：
最少步数 -> BFS，首次到达即为最短
任一可行解 -> 回溯，成功后立即返回
全部答案 -> 回溯，命中后继续探索
扩展状态前：
排除违反硬约束的选择
排除已经访问的状态
合并彼此等价的选择
借助索引结构判断某条前缀是否仍有希望
执行选择
递归或入队
若是路径状态，撤销选择
模板变体
状态空间与目标类型
无权图最短路天然按层扩展，适合 BFS；数独只要求一个可行解，递归返回布尔值可以沿成功路径提前结束；网格多词匹配需要收集全部答案，因此命中一个词后仍要继续沿 Trie 向下。
不可能分支
数独中，某数字已经出现在同行、同列或同宫，这个选择立即非法。等和分桶中，桶和超过目标也不可能通过后续正数修复。越早检查确定不可能的条件，越少产生无意义子树。
等价选择
若两个桶当前容量相同，把当前数字放入任意一个桶会得到对称状态，只尝试其中一个即可。这里去重的是“下一状态”，不是在得到最终结果后再用集合清洗。
辅助结构
单词搜索 II 使用 Trie 把共享前缀合并起来。网格路径一旦不在 Trie 中，就能同时排除所有具有该前缀的候选词；这比为每个单词单独搜索一次更接近问题本身的重复结构。
母题序列
按拓展顺序练习：
- 单词接龙：把单词看作无权状态图，用 BFS 求最短转换序列。
- 解数独：同步维护行、列、宫三类约束，并在失败时完整撤销。
- 划分为 k 个相等的子集：降序放置数字，以容量上界和等价桶剪枝。
- 单词搜索 II：用 Trie 合并共享前缀，在一次网格搜索中匹配多个单词。
常见误区
- BFS 出队后才标记访问，导致同一状态在同一层被重复加入队列。
- 只恢复棋盘，却忘记恢复行、列或宫的占用信息，使后续分支继承错误状态。
- 把分桶问题写成状态压缩动态规划，超出本节的回溯与剪枝训练目标。
- 为单词表中的每个词分别运行一次网格 DFS，没有利用共享前缀。
- 将“复杂算法”误认为“剪枝越多越好”；没有证明安全性的剪枝可能直接删掉正确答案。
迁移方向
综合搜索首先迁移的是建模方式：无权最短路优先考虑 BFS，约束满足问题考虑回溯，等价选择考虑对称性剪枝，多模式前缀考虑 Trie。进一步的双向 BFS、精确覆盖、状态压缩动态规划或自动机属于更高阶工具；在进入这些方法前，应先能说明当前状态、转移和每条剪枝为什么正确。