组合总和
回溯与搜索 · 决策树剪枝
凑出目标和
给一组数 [1, 2, 3, 4] 和一个目标 5，从中选出若干个（每个数最多用一次），使它们的和恰好等于目标——列出所有这样的组合。这里的答案是 {1, 4} 和 {2, 3}。这仍是回溯，但它引出了回溯真正高效的关键：剪枝。
剪枝：不去走注定失败的路
我们仍在一棵决策树上搜索：每一步再加入一个数（为避免重复，只从后面的数里选）。但和前几页不同，这里每个节点都带一个当前和。一旦加入某个数使当前和超过目标，这条分支再往下走也不可能成解——于是直接砍掉它、不再展开。这就是剪枝：提前判断死路，避免徒劳的搜索。
下面是候选 [1, 2, 3, 4]、目标 5 的决策树。点「下一步」逐步看：每条边表示加入了哪个数、节点显示当前和；和 = 5 的节点标绿（一个解），和 > 5 的分支标红剪掉（剪枝，不再展开），其余继续深入；一支走完就回溯换下一个数。留意有多少分支被剪枝提前砍掉——这正是剪枝省下的搜索。右侧代码随每一步同步高亮。
空组合，和 0，逐个加数凑目标 5
1function combinationSum(cands: number[], target: number): number[][] {
2 const res: number[][] = [];
3 const cur: number[] = [];
4 const backtrack = (start: number, sum: number): void => {
5 if (sum === target) {
6 res.push([...cur]);
7 return;
8 }
9 for (let i = start; i < cands.length; i++) {
10 if (sum + cands[i] > target) continue; // 剪枝：加上去会超目标
11 cur.push(cands[i]);
12 backtrack(i + 1, sum + cands[i]);
13 cur.pop(); // 撤销（回溯）
14 }
15 };
16 backtrack(0, 0);
17 return res;
18}
候选1 2 3 4
目标5
当前组合∅
当前和0
已找到0
1 / 24
剪枝不改变答案，只砍掉不可能有答案的分支，让搜索规模大幅缩小。好的剪枝往往是回溯能否跑得动的关键——N 皇后 里「与已放皇后冲突就换一行」其实也是一种剪枝。本页的判据最直白：当前和 > 目标就砍。
回溯三要素，到此凑齐
回溯 = 试探（往下做一个选择）+ 剪枝（提前否掉注定失败的分支）+ 回溯（撤销选择、退回去换一个）。
N 皇后：棋盘约束试探 + 冲突剪枝。子集：选/不选（无剪枝，全枚举）。
全排列：已用元素剪枝。组合总和：超目标剪枝——把「剪枝」讲到最直观。
N 皇后：棋盘约束试探 + 冲突剪枝。子集：选/不选（无剪枝，全枚举）。
全排列：已用元素剪枝。组合总和：超目标剪枝——把「剪枝」讲到最直观。
同一套 DFS 骨架，配上不同的选择集与剪枝规则，就能解决约束满足、组合枚举、路径搜索一大类问题——这就是回溯与搜索的通用力量。