搜索与回溯

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

各段是独立 main.go，在新模块中只保存当前一个例子；本轮未执行，下面输出按搜索顺序静态推导。n、k 等数量需非负且输入规模足够小；组合选自 1..n，重复值排列不会自动去重。数独初盘需合法、只含点号或 1..9；无解会返回 false，迷宫无路返回空路径。

要解决的问题	可选方法	选择前确认
枚举任意选择、固定数量选择或全部顺序	子集枚举、组合、全排列	子集有 2ⁿ 个，排列有 n! 个；组合通过递增候选下标避免顺序重复。
尽早停止无法达到目标的分支	剪枝	子集和示例依赖非负元素；含负数时当前和超过目标仍可能被抵消。
生成合法括号或放置互不冲突的皇后	括号生成或N 皇后	在扩展时检查左右括号数量，或列与对角线占用；返回后撤销选择。
填满带行、列和宫格约束的棋盘	数独求解	示例找到第一组解即返回；初始棋盘合法性仍须检查。
在网格中寻找一条可行路径	迷宫 DFS	访问标记避免重复进入，回溯维护路径；若要最短步数，应使用 BFS。

区分子集、组合与排列的搜索空间

子集枚举

正文、推演与完整示例：子集枚举。

位移宽度受整数位数限制；很大的 n 应使用递归或迭代扩展且避免一次保存所有结果。

组合

正文、推演与完整示例：组合。

可加入“剩余候选不足”判断，减少不可能完成的分支。

全排列

正文、推演与完整示例：全排列。

输出本身有 n! 个，输入稍大就会迅速增长；重复元素还需去重规则。

用可证明的边界跳过无解分支

剪枝

正文、推演与完整示例：剪枝。

这段回溯是在求子集和：每个元素只有选或不选两个分支。剪枝依赖元素非负；例如输入 {5,-2}、目标 3 时，选 5 后虽然超过目标，后面的 -2 仍能抵消，直接剪掉这条分支就会漏解。

有效剪枝必须建立在可证明的上下界上。

边构造边检查括号与棋盘约束

括号生成

正文、推演与完整示例：括号生成。

到长度 2n 时得到完整答案，不需要先生成非法串再过滤。

N 皇后

正文、推演与完整示例：N 皇后。

搜索仍可能指数增长，但即时排除冲突位置比先枚举整张棋盘高效得多。

数独求解

正文、推演与完整示例：数独求解。

示例返回找到的第一组解；实际应用还应检查初始棋盘是否已违反规则。

在迷宫中维护访问状态与路径

迷宫搜索

正文、推演与完整示例：迷宫搜索。

DFS 找到的是一条路径，不保证步数最短，最短路应使用 BFS。

静态自检

HasSubsetSum 对含负数数组还能用 sum>target 剪枝吗？提示：用 {5,-2}、目标 3 追踪首条分支。

参考解法

不能；选 5 后当前和超过 3，但后续 -2 能抵消得到解。当前实现前提为非负输入，不能删掉该前提后仍声称剪枝正确。