剪枝

搜索最怕做无用功。如果走到某一步，已经能断定这条路无论如何都出不了答案，就立刻 return，别再往下白跑。这就是剪枝，是搜索从"能过样例"到"能过大数据"的关键。

比如找若干数之和恰好为 10 的组合，当前和一旦超过 10，再往下加只会更大，直接砍掉这条分支：

void dfs(int start, int sum) {
    if (sum > 10) return;         // 剪枝：已经超了，没戏
    if (sum == 10) { 记录答案; return; }
    for (int i = start; i <= n; i++)
        dfs(i + 1, sum + a[i]);
}

剪枝不改变正确答案，只跳过注定失败的分支。一个好的剪枝，常常能把要跑几分钟的搜索压到零点几秒。