组合总和

回溯与搜索 · 决策树剪枝

凑出目标和

给一组数 [1, 2, 3, 4] 和一个目标 5，从中选出若干个（每个数最多用一次），使它们的和恰好等于目标——列出所有这样的组合。这里的答案是 {1, 4} 和 {2, 3}。这仍是回溯，但它引出了回溯真正高效的关键：剪枝。

剪枝：不去走注定失败的路

我们仍在一棵决策树上搜索：每一步再加入一个数（为避免重复，只从后面的数里选）。但和前几页不同，这里每个节点都带一个当前和。一旦加入某个数使当前和超过目标，这条分支再往下走也不可能成解——于是直接砍掉它、不再展开。这就是剪枝：提前判断死路，避免徒劳的搜索。

下面是候选 [1, 2, 3, 4]、目标 5 的决策树。点「下一步」逐步看：每条边表示加入了哪个数、节点显示当前和；和 = 5 的节点标绿（一个解），和 > 5 的分支标红剪掉（剪枝，不再展开），其余继续深入；一支走完就回溯换下一个数。留意有多少分支被剪枝提前砍掉——这正是剪枝省下的搜索。右侧代码随每一步同步高亮。

剪枝不改变答案，只砍掉不可能有答案的分支，让搜索规模大幅缩小。好的剪枝往往是回溯能否跑得动的关键——N 皇后 里「与已放皇后冲突就换一行」其实也是一种剪枝。本页的判据最直白：当前和 > 目标就砍。

回溯三要素，到此凑齐

同一套 DFS 骨架，配上不同的选择集与剪枝规则，就能解决约束满足、组合枚举、路径搜索一大类问题——这就是回溯与搜索的通用力量。