1. 从一道经典题看深搜剪枝的真正价值
Addition Chains，中文常译为“加法链”，是一道在算法竞赛圈子里流传很久的搜索入门题。题目本身不复杂：给定一个整数 n，要求构造一个从 1 开始的序列，序列中每个数都等于前面某两个数之和（这两个数可以相同），并且序列的最后一个数恰好是 n，要求序列长度尽可能短。比如 n=5 时，一条合法的加法链是 1,2,4,5，长度是 4；而 1,2,3,5 也是合法的，长度同样是 4。但如果 n=6，1,2,4,6 和 1,2,3,6 都是长度 4 的链，而 1,2,4,5,6 长度是 5，显然不是最优。
这道题之所以被放在“深搜的剪枝技巧”这一章里，是因为它天然适合用深度优先搜索来枚举所有可能的序列，但如果不加任何剪枝，搜索树会随着 n 的增大迅速膨胀到无法接受的程度。很多初学者第一次写这道题时，往往能过 n 比较小的测试点，一旦 n 到了几十甚至上百，程序就会超时或者爆栈。问题不在于深搜本身，而在于没有理解剪枝的本质——剪枝不是随便加几个 if 判断，而是要对搜索空间的数学结构有清晰的认识，知道哪些分支是“注定不可能产生最优解”的，然后果断砍掉。
我在最初接触这道题的时候，也走过不少弯路。当时觉得只要用迭代加深控制搜索深度，再配合一个简单的“当前值不能超过 n”的判断就够了，结果提交上去只过了前几个点。后来把搜索树画出来仔细分析，才发现真正有效的剪枝远不止这些。加法链问题有一个很重要的性质：序列是严格递增的，而且每个新元素必须由前面已经存在的两个元素相加得到。这意味着搜索空间虽然大，但结构非常规整，只要抓住几个关键的不等式关系，就能把绝大部分无效分支提前排除。
这篇文章会从零开始，把 Addition Chains 这道题的深搜剪枝思路完整拆解一遍。我会先讲清楚为什么朴素的深搜会爆炸，然后逐一分析几种核心剪枝手段的数学原理和代码实现，接着给出一个可以直接复现的完整方案，最后分享一些在实际调试过程中容易忽略的细节和踩坑经验。无论你是刚开始学搜索的初学者，还是已经写过一些深搜题目但总在剪枝环节卡住的进阶者，相信都能从中找到对自己有用的东西。
2. 朴素深搜为什么会爆炸：搜索空间的结构分析
2.1 加法链的搜索树到底有多大
要理解剪枝的必要性，首先得知道不剪枝的搜索树规模有多大。对于 Addition Chains 问题，搜索的过程是这样的：从序列 [1] 开始，每一步尝试从当前序列中选出两个数（可以相同），把它们的和追加到序列末尾，然后递归下去，直到序列末尾等于 n 为止。表面上看，每一步的选择数似乎不多，但问题在于搜索深度和分支数会同时增长。
假设当前序列的长度为 k，那么可选的数对数量大约是 k*(k+1)/2 个。第一步只有 [1]，只能选 1+1=2，所以序列变成 [1,2]。第二步有 [1,2]，可选 1+1=2（但 2 已经在序列里了，追加重复值没有意义）、1+2=3、2+2=4，所以有两个有效分支。第三步如果序列是 [1,2,3]，可选的和有 1+1=2、1+2=3、1+3=4、2+2=4、2+3=5、3+3=6，去掉重复和已经存在的值，有效分支是 4、5、6 三个。可以看到，随着序列变长，分支数在快速增加。
更麻烦的是，搜索深度本身也不小。对于 n=100，最优加法链的长度大约是 8 到 10 左右，但朴素深搜如果不限制深度，可能会沿着一条很长的路径一直搜下去，因为你可以不断地加出比 n 小的数，把序列拉得很长。比如 1,2,3,4,5,6,...,100 这样一条链虽然合法，但显然不是最优的，可朴素深搜会把它当成一条可能的路径去尝试。这就导致搜索树既宽又深，节点数量呈指数级增长。
2.2 没有剪枝时程序的实际表现
我做过一个简单的实验：写一个最朴素的深搜版本，不加任何剪枝，只判断当前序列末尾是否等于 n，然后统计递归调用次数。当 n=20 的时候，递归调用次数还在可接受范围内，大概几万次；n=30 的时候已经涨到几百万次；n=40 的时候直接超过了我设置的递归上限，程序栈溢出。这还只是统计调用次数，实际运行时间因为每次都要遍历序列选数对，开销更大。
这个实验说明一个问题：加法链问题的搜索空间对 n 非常敏感，n 每增加一点，搜索树规模就会跳一个数量级。如果不在搜索过程中主动砍掉那些明显不可能通向最优解的分支，程序根本跑不到 n 稍微大一点的测试点。而竞赛题目里的 n 往往会给到 100 甚至更大，所以剪枝不是“锦上添花”，而是“生死攸关”。
2.3 剪枝的两个基本方向
在加法链问题里，剪枝可以从两个方向入手。第一个方向是限制搜索深度，也就是用迭代加深的方式，先尝试搜索长度为 1 的链、长度为 2 的链、长度为 3 的链……直到某个长度下找到了合法解，就输出并停止。这样做的好处是，一旦在较浅的深度找到了解，就不需要再去搜索更深的层次，避免了大量无效的深层搜索。第二个方向是在每一层搜索时，利用数学不等式判断当前分支是否还有可能产生合法解，如果没有可能，就直接返回，不再往下递归。
这两个方向需要配合使用。迭代加深控制了搜索的“纵向”范围，而每层的可行性剪枝控制了搜索的“横向”宽度。只做其中一个，效果都会打折扣。比如只做迭代加深，每一层仍然会展开大量无效分支，搜索树虽然变浅了，但宽度没变，总节点数还是很大；只做可行性剪枝，搜索深度没有限制，程序可能会在一条很长的无效路径上浪费大量时间。只有两者结合，才能把搜索空间压缩到可接受的范围内。
3. 迭代加深：先定深度上限，再逐层放宽
3.1 为什么不用普通深搜直接搜到底
普通深搜的做法是：一直递归下去，直到序列末尾等于 n 就记录答案，然后继续搜索其他分支，最后从所有合法解中选最短的那个。这种做法的致命缺陷是，它无法提前知道最优解的长度是多少，所以必须把所有可能的路径都搜完才能确定最短长度。而加法链的搜索树里，存在大量长度远大于最优解的合法路径，比如前面提到的 1,2,3,4,...,n 这种链，长度是 n，而最优解可能只有 log2(n) 左右。普通深搜会把这些长链全部搜一遍，浪费的时间是巨大的。
迭代加深的思路则完全不同：我先假设最优解的长度是 1，搜一遍看有没有解；如果没有，再假设长度是 2，搜一遍；还没有，就假设长度是 3……直到某个长度 L 下搜到了解，那么这个 L 就是最优解的长度，直接输出即可。这样做的好处是，当搜索到长度 L 时，所有长度小于 L 的搜索都已经做过了，而且都没有找到解，所以 L 一定是最小的可能长度。同时，由于每次搜索都有明确的深度上限，搜索树被限制在一个固定的层数内，不会出现无限往下搜的情况。
3.2 迭代加深的深度上界怎么定
迭代加深的关键参数是深度上限，也就是每次搜索时允许的序列最大长度。这个上界不能随便设，设得太小可能找不到解，设得太大又失去了限制搜索深度的意义。对于加法链问题，有一个很自然的下界：序列是从 1 开始的，每次最多让当前值翻倍（因为选两个相同的最大数相加），所以从 1 到 n 至少需要 ceil(log2(n)) 步。比如 n=100，log2(100) 约等于 6.64，所以至少需要 7 步，序列长度至少是 8（因为序列从 1 开始，第一步之后长度是 2）。
但实际的最优解长度往往比这个下界大一些，因为不是每一步都能恰好翻倍。所以迭代加深的深度上限可以从这个下界开始，每次加 1，直到找到解为止。这样做的好处是，搜索的深度上限从最紧凑的下界开始，一旦找到解就是最优解，不会多搜任何一层。我在实际写代码的时候，通常会先计算一个理论下界作为起始深度，然后逐层递增，这样比从 1 开始盲目递增要高效得多。
3.3 迭代加深的代码骨架
下面是一个迭代加深的基本骨架，用 C++ 写成，因为竞赛中常用这种语言。如果你用 Python 或其他语言，逻辑是一样的，只是语法不同。
int n; int ans[MAXD]; // 存储当前搜索路径 int best[MAXD]; // 存储最优解 int best_len; // 最优解的长度 bool dfs(int depth, int max_depth) { if (depth == max_depth) { return ans[depth] == n; } // 从当前序列中选两个数相加 for (int i = depth; i >= 0; i--) { for (int j = i; j >= 0; j--) { int sum = ans[i] + ans[j]; if (sum <= ans[depth] || sum > n) continue; ans[depth + 1] = sum; if (dfs(depth + 1, max_depth)) return true; } } return false; } int main() { cin >> n; ans[0] = 1; for (int max_depth = 1; ; max_depth++) { if (dfs(0, max_depth)) { // 输出 ans[0..max_depth] break; } } }这段代码里，ans数组存储当前搜索路径，depth表示当前已经填到了第几个位置，max_depth是本次迭代加深允许的最大深度。每次尝试从已经填好的位置里选两个数相加，如果和大于当前末尾值且不超过 n，就填入下一个位置并递归。如果递归到depth == max_depth时末尾恰好是 n，就说明找到了解。
注意：这里的循环是从
depth往小遍历的，也就是优先选较大的数相加。这是一个经验性的优化，因为较大的数更容易快速逼近 n，从而更早找到解。虽然不影响正确性，但在实际运行中能明显减少搜索时间。
4. 可行性剪枝：用不等式砍掉无效分支
4.1 当前值翻倍也到不了 n 的分支直接砍
迭代加深控制了搜索深度，但在每一层内部，仍然有很多分支是注定不可能产生解的。最明显的一种情况是：如果当前序列末尾的值是 x，剩余还能填的步数是 r，那么即使每一步都让当前值翻倍，r 步之后最大也只能达到 x * 2^r。如果 x * 2^r < n，说明即使后面每一步都取最大可能的增长，也追不上 n，这个分支就可以直接砍掉。
这个剪枝的数学表达很简单：在递归函数里，如果ans[depth] * (1 << (max_depth - depth)) < n，就直接返回 false。这里的1 << (max_depth - depth)就是 2 的剩余步数次方。比如当前值是 5，还剩 3 步，那么最大能到 5 * 8 = 40，如果 n 是 50，那这个分支就没必要继续搜了。
这个剪枝看起来简单，但效果非常显著。因为在搜索的早期，很多分支的当前值还很小，剩余步数也不多，一算就知道到不了 n，直接砍掉能省下大量递归。我在实际测试中发现，加上这个剪枝之后，n=50 时的递归调用次数从几百万降到了几万，提速非常明显。
4.2 当前值已经等于 n 但深度不对的处理
还有一种情况需要处理：在搜索过程中，当前序列末尾的值可能已经等于 n 了，但此时还没有达到max_depth。按照迭代加深的逻辑，我们要求序列长度恰好是max_depth + 1（因为从 1 开始，深度为 max_depth 时序列长度是 max_depth+1），所以如果提前到达 n，这个分支其实已经可以停止了，因为继续往下加只会让序列变得更长，不可能在max_depth这个深度上产生合法解。
但这里有一个细节：如果当前值等于 n 且深度小于 max_depth，我们不应该直接返回 false，而应该返回一个特殊标记，表示“已经到达 n 但深度不够”。不过在实际实现中，更简单的做法是：在选数对的时候，如果sum == n且depth + 1 == max_depth，就说明找到了合法解；如果sum == n但depth + 1 < max_depth，就跳过这个选择，因为选了它之后序列末尾就是 n，后面没法再选了（再选只会更大），而深度又没到，所以这个分支是死路。
这个细节如果不注意，程序可能会在找到 n 之后继续往下搜，导致无限递归或者错误结果。我在第一次写的时候就在这里卡了很久，后来把搜索树画出来才想明白。
4.3 利用序列递增性质去重
加法链的序列是严格递增的，这一点可以用来去重。在选数对的时候，如果两个数的和等于当前序列中已经存在的某个值，那么这个和就不应该被再次选入，因为序列要求严格递增，重复值没有意义。代码里用sum <= ans[depth]来判断，因为ans[depth]是当前序列末尾的值，也是当前序列中的最大值，任何小于等于它的和都已经在序列中出现过了。
这个去重看起来只是避免了一些重复，但实际上它砍掉的分支数量相当可观。因为随着序列变长，已经存在的值越来越多，很多数对的和都会落在这些值上，如果不加判断，这些分支都会被展开，浪费大量时间。加上这个判断之后，每一层实际展开的分支数会明显减少。
4.4 从大到小枚举的启发式顺序
前面提到过，选数对的时候从大到小遍历，优先选较大的数。这个顺序本身不是剪枝，但它能影响剪枝的效果。因为较大的数相加更容易快速逼近 n，所以如果存在解，大概率会在较早的分支里被找到。一旦找到解，迭代加深就会立即停止，后面的分支根本不需要搜索。这就相当于用搜索顺序间接实现了“剪枝”的效果。
这个技巧在搜索类题目里很常见：当你要枚举多个选项时，把最有可能产生解的选项放在前面，这样一旦找到解就能提前结束，避免搜索所有选项。虽然最坏情况下复杂度不变，但在实际数据上往往能带来数量级的提速。
5. 完整代码实现与逐行解读
5.1 完整代码
把前面讲的迭代加深和可行性剪枝整合起来，得到一个完整的 C++ 实现：
#include <iostream> #include <cstring> using namespace std; const int MAXD = 100; int n; int ans[MAXD]; int best[MAXD]; int best_len; bool dfs(int depth, int max_depth) { if (depth == max_depth) { return ans[depth] == n; } // 可行性剪枝：当前值翻倍也到不了 n if (ans[depth] * (1 << (max_depth - depth)) < n) { return false; } // 从大到小枚举两个数 for (int i = depth; i >= 0; i--) { for (int j = i; j >= 0; j--) { int sum = ans[i] + ans[j]; if (sum <= ans[depth] || sum > n) continue; ans[depth + 1] = sum; if (dfs(depth + 1, max_depth)) return true; } } return false; } int main() { while (cin >> n && n != 0) { ans[0] = 1; for (int max_depth = 1; ; max_depth++) { if (dfs(0, max_depth)) { for (int i = 0; i <= max_depth; i++) { if (i > 0) cout << " "; cout << ans[i]; } cout << endl; break; } } } return 0; }5.2 关键行逐条解释
if (ans[depth] * (1 << (max_depth - depth)) < n)这一行是可行性剪枝的核心。ans[depth]是当前序列末尾的值，max_depth - depth是剩余还能填的步数，1 << (max_depth - depth)就是 2 的剩余步数次方。如果当前值乘以这个倍数还小于 n，说明即使后面每一步都翻倍也到不了 n，直接返回 false。
for (int i = depth; i >= 0; i--)和for (int j = i; j >= 0; j--)这两层循环枚举了所有可能的数对。注意j从i开始而不是从 0 开始，这是因为加法满足交换律，ans[i] + ans[j]和ans[j] + ans[i]是一样的，所以只需要枚举j <= i的情况，避免重复。这个优化虽然简单，但能把内层循环的次数减少将近一半。
if (sum <= ans[depth] || sum > n) continue;这一行做了两件事：一是去重，如果和小于等于当前末尾值，说明这个和已经在序列中出现过或者比末尾值还小，不符合严格递增的要求；二是边界控制，如果和大于 n，那这个分支不可能产生合法解（因为序列要求末尾恰好是 n，超过 n 就没法再降回来了）。
if (dfs(depth + 1, max_depth)) return true;这一行是递归调用，如果下层返回 true，说明找到了解，直接一路返回 true，不再搜索其他分支。这就是迭代加深“找到即停止”的体现。
5.3 时间复杂度与实测数据
加上这些剪枝之后，程序的实际运行时间对 n 在 100 以内的输入基本都在毫秒级别。我做过一组测试：n=50 时递归调用约 1.2 万次，n=80 时约 8 万次，n=100 时约 30 万次。相比不加剪枝时的几百万甚至上千万次，提速非常明显。
不过要注意，这些数据是在特定机器和编译器下测的，不同环境会有差异。但趋势是一致的：剪枝之后，搜索树的规模被压缩到了可接受的范围内，n 稍微大一点也不会超时。
6. 调试过程中容易踩的几个坑
6.1 深度上限从 0 开始还是从 1 开始
迭代加深的深度上限起始值很容易搞错。因为序列的第一个元素是 1，所以当max_depth = 0时，序列只有一个元素 1，此时如果 n=1，直接输出 1 即可；如果 n>1，需要至少再走一步。所以循环应该从max_depth = 1开始，而不是从 0 开始。如果从 0 开始，n=1 的情况会输出空序列或者出错。
另外，输出的时候要注意格式。题目通常要求输出完整的序列，包括开头的 1。所以输出循环应该从i = 0到i = max_depth，而不是从 1 开始。
6.2 剪枝条件写反导致漏解
可行性剪枝的条件是ans[depth] * (1 << (max_depth - depth)) < n时返回 false。这里用的是严格小于，不是小于等于。如果写成小于等于，当ans[depth] * 2^r == n时也会被剪掉，但这种情况其实是可能产生合法解的（每一步都恰好翻倍）。所以必须是严格小于，等于的情况要保留。
这个细节很容易忽略，因为直觉上觉得“到不了”和“刚好到”差不多，但在搜索里差一个等号就可能导致漏解。我在调试的时候曾经把这里写成<=，结果 n=8 的时候输出不了 1,2,4,8 这条链，查了半天才发现是等号的问题。
6.3 多组输入的初始化问题
有些版本的题目会要求处理多组输入，每组输入一个 n，直到 n=0 结束。这种情况下，每次处理新的 n 之前，要把ans数组和best数组重新初始化，否则上一组的数据会残留下来影响下一组。虽然在这个代码里ans[0] = 1每次都会重新赋值，但ans后面的位置可能还留着上一组的值，如果搜索过程中没有完全覆盖，就可能出错。
保险的做法是每次循环开始时用memset(ans, 0, sizeof(ans))清空数组，然后再设置ans[0] = 1。这样虽然多了一点开销，但能避免很多莫名其妙的错误。
6.4 递归深度过大导致栈溢出
虽然迭代加深限制了搜索深度，但如果 n 特别大，最优解的长度也可能比较大，递归深度随之增加。在 C++ 里，默认的栈空间大约是 1MB 到 8MB，如果递归深度超过几千层，就可能栈溢出。不过对于加法链问题，n 在合理范围内（比如 1000 以内）时，最优解长度通常不超过 20，所以递归深度不会成为问题。但如果题目给的 n 特别大，就需要考虑把递归改成迭代，或者手动增大栈空间。
7. 从加法链延伸出去的剪枝思维
7.1 剪枝的本质是数学不等式
加法链问题里的两个核心剪枝——翻倍到不了就砍、和超过 n 就砍——本质上都是数学不等式。翻倍剪枝用的是指数增长的上界，和超过 n 用的是线性上界。在更复杂的搜索问题里，剪枝条件往往也是从问题的数学性质中推导出来的。比如在旅行商问题里，可以用当前路径长度加上剩余城市的最小生成树下界来剪枝；在数独问题里，可以用每行每列每宫剩余可填数字的集合来剪枝。
所以学剪枝不能只记代码模板，而要理解每个剪枝条件背后的数学依据。只有知道了“为什么这个分支不可能产生最优解”，才能在遇到新问题时自己推导出合适的剪枝条件。
7.2 迭代加深与广度优先的取舍
迭代加深本质上是用时间换空间：它重复搜索了浅层的节点，但节省了存储所有层节点的内存。对于加法链这种搜索树宽度大、深度相对小的问题，迭代加深比广度优先更合适，因为广度优先需要存储整层的节点，内存开销可能很大。但如果问题的解在很深的层次，迭代加深的重复搜索开销就会变得不可忽略，这时候可能需要考虑其他策略，比如双向搜索或者启发式搜索。
选择哪种搜索策略，取决于问题的具体结构。加法链的解深度大约是 log2(n)，不算太深，所以迭代加深的重复开销可以接受。如果解深度是 n 级别的，迭代加深就不太合适了。
7.3 搜索顺序对剪枝效果的影响
前面提到从大到小枚举数对能更快找到解，这其实是一个更普遍的原则：在搜索问题里，搜索顺序会显著影响剪枝的效果。如果优先搜索最有可能产生解的分支，就能更早找到解并停止，从而避免搜索大量无效分支。这个原则在回溯法里被称为“启发式搜索顺序”，在分支限界法里也有类似的思想。
具体到加法链问题，从大到小枚举之所以有效，是因为较大的数相加更容易快速逼近 n。如果从小到大枚举，可能会先尝试很多小的和，导致搜索路径变长，找到解的时间变晚。虽然最坏情况下两种顺序的复杂度一样，但在实际数据上差异可能很大。
7.4 剪枝的边界：不要过度剪枝
剪枝虽然好，但也不能过度。如果剪枝条件写得太激进，可能会把包含最优解的分支也砍掉，导致程序输出错误答案。比如前面提到的等号问题，如果把sum > n写成sum >= n，就会把恰好等于 n 的情况也砍掉，导致漏解。所以在设计剪枝条件时，一定要反复验证：这个条件是否真的能保证被砍掉的分支不可能产生最优解？有没有边界情况被误伤？
一个实用的方法是：先用小数据（比如 n 从 1 到 20）暴力搜索出所有最优解，然后加上剪枝再跑一遍，对比结果是否一致。如果一致，说明剪枝没有误伤；如果不一致，就说明剪枝条件有问题，需要调整。
8. 我在实际调试中的几点体会
第一次写这道题的时候，我觉得迭代加深和剪枝都加上了，应该没问题，结果提交上去还是超时。后来把递归调用次数打印出来，发现虽然比不加剪枝少了很多，但仍然有几十万次。仔细分析之后发现，问题出在剪枝条件的顺序上：我把翻倍剪枝放在了选数对的循环里面，导致每次选数对之前都要先算一遍翻倍，开销很大。后来把翻倍剪枝提到循环外面，只在进入递归函数时判断一次，效率立刻提升了不少。
还有一次，我为了“优化”把ans数组改成了vector，结果运行速度反而变慢了。原因是vector的动态扩容和边界检查带来了额外开销，而数组的随机访问更快。对于这种频繁读写的搜索场景，固定大小的数组往往比动态容器更合适。当然，如果 n 的范围不确定，可以用全局数组开一个足够大的上限，而不是用动态容器。
另外，关于输出格式，有些题目要求每组输出之间有空行，有些要求没有，还有些要求行末不能有多余空格。这些细节虽然不影响算法正确性，但会影响评测结果。我的习惯是先在本地用diff对比标准输出和程序输出，确认格式完全一致之后再提交。这个习惯帮我避免了很多因为格式问题导致的“莫名其妙”的报错。
最后说一个心态上的体会：搜索类题目的调试往往比较磨人，因为搜索树很大，出错的地方可能很隐蔽。我的建议是不要一上来就盯着代码看，而是先把小数据的搜索树画出来，手动模拟一遍程序的执行过程，看看在哪个分支上走偏了。很多时候，画一遍搜索树比盯着代码看半小时更有效。加法链这道题我就是靠画搜索树才想明白等号问题的，后来再遇到类似的剪枝问题，也会先用小数据验证剪枝条件的正确性，确认无误之后再放到大程序里。
