基本剪枝技巧

考虑一个简单的选数求和问题：从一些给定的、有重复的数 $a_1,a_2,...,a_n$ 中，允许选最少的几个数，使之和为一个定值 $s$。

1. 搜索顺序优化

在大部分搜索问题中，搜索树并不是完全树，这意味着有的分支浅，有的分支深，而且无论是深的分支还是浅的分支都有可能搜到结果上相同的状态，这启示我们应该先从较浅的分支探索。例如在选数求和问题中，一条可行的经验是，先排序，然后从较大的数开始试。

2. 重复性剪枝

搜索过程中，如果可以判定几条分支是完全等效的，那么只需要对其中一条分支搜索即可。例如在选数问题中，对于相同的数，一旦判定其中一个不符合要求，那么之后遇到这个数就也可以跳过了。

3. 最优性剪枝

常见于要求最小/最优的搜索问题中，如果当前花费的代价已经大于目前搜到的最优解，那么无论如何都不可能再得到更优的结果，因此应当停止对当前分支的搜索，立刻回溯。例如在选数求和问题中，目前凑出 $k$ 需要最少的数是 $3$ 个，而当前搜索已经用了 $3$ 个数还未能达到 $k$，那么就可以回溯了。

4. 可行性剪枝

如果发现分支无法到达递归边界，则应当回溯。遇到一个搜索问题，先考虑能否在搜索前通过预处理剪枝，再考虑搜索时如何检查能否到达递归边界。例如在选数求和问题中，如果存在一些数大于 $k$，那么应当将这些数排除。在搜索时，如果发现当前和已经大于 $k$ 或当前和加上之后数的和仍然小于 $k$，则应当回溯。

题目

因为sanhai_oj几乎没有题目，所以以下题目来自luogu。

P1120 小木棍；

P1074 [NOIP 2009 提高组] 靶形数独；

P2329 [SCOI2005] 栅栏；

P10482 Sudoku 2。

希望sanhai_oj可以做得更好，拥有更多的题目。