阶乘和算法题精讲：暴力回溯、贪心证明与0!陷阱全解析

1. 题目精读：阶乘和问题的真正考点是什么

这道题编号 3481，名字就叫"阶乘的和"。题面的核心意思可以概括成一句话：给你一个正整数 n，问能不能把它拆成若干个不同非负整数的阶乘之和，能的话给出一种拆分方案，不能就返回无解。我第一次看到这个题名时，心里想的是"阶乘加起来有什么好考的"，真正动手以后才发现，坑全藏在那些"你以为自己会但其实没注意"的环节里——0! 和 1! 的值撞车、阶乘候选的截断、贪心正确性的证明，每一个都能让你在本地跑得爽爽的，提交上去却输得莫名其妙。

先把地基打好，阶乘的数值表是这题最重要的工具。0! = 1，1! = 1，2! = 2，3! = 6，4! = 24，5! = 120，6! = 720，7! = 5040，8! = 40320，9! = 362880，10! = 3628800，11! = 39916800，12! = 479001600，13! = 6227020800。注意几个反直觉的地方：第一，0! 和 1! 都等于 1，这俩在"不同下标"的约束下是两项，但值完全相同；第二，这个序列从 4! 开始暴涨，每一项大约是前一项的 i 倍，12! 到 13! 直接翻了 13 倍；第三，候选个数非常少，绝大多数数据范围下根本不需要处理超过 20 个元素。这三点合在一起，决定了这道题既不能"瞎枚举所有整数"，也不需要上什么高级数据结构。

我个人拿到题的习惯是，先不看代码，拿笔把三个问题写下来：输入范围是多少、输出要求什么东西、同一个阶乘能不能重复用。前两个决定算法选型，第三个是这题最容易埋暗坑的地方。这篇文章适合两类人读：一类是刚接触这类"数值拆分"题、想搞懂从暴力到贪心完整推导链路的选手；另一类是已经会写、但被 0! 和 1! 或整数溢出坑过、想找一份系统复盘的老手。无论你属于哪类，跟着我的完整思路走一遍，收获绝对比背一份题解大得多。

1.1 先拿数据范围做复杂度估算，再决定动不动手

假设题目给定的 n 上限是 10^9，那小于等于这个数的最大阶乘是 12! = 479001600，13! = 6227020800 已经超了，所以候选集合最多只有 13 个数。13 个元素，每个选或者不选，一共 2^13 = 8192 种组合，暴力枚举连优化都不用做。就算出题人把上限放大到 10^18，候选也只是 0 到 19 的阶乘，2^20 约一百万种，依然在可接受范围内。

这个"把看似无穷的问题截断成有限候选"的思想，是整道题最值钱的地方。很多人一看到 n 很大就慌，觉得是不是要用数学公式、要上数论定理，其实阶乘这种超指数增长的序列天然帮你把搜索空间压缩到了极致。你要做的只是找到那个"第一个超过 n 的阶乘"，然后它前面的所有项就是你的整个战场。这个习惯养成了，以后遇到"给定大数、候选是小集合"的题目，你都会条件反射地先做截断，而不是硬着头皮搜。

1.2 输出要求的不同形态，直接决定你该写回溯还是位运算

同样是问"阶乘的和"，有的版本只要返回能不能，有的版本要求返回具体是哪几个阶乘。如果是后者，强烈建议写递归回溯而不是位运算枚举。位运算枚举确实快，但你要把所有被选中的二进制位反推回阶乘下标，中间那层映射关系特别容易写错，尤其是位数超过 10 以后，肉眼根本分不清某一位对应的是哪个阶乘。回溯天然带着当前路径，选了什么一目了然，调试体验好太多。

复杂度上两者完全没差别——反正在候选只有十几个的前提下都是瞬时完成。做题不是炫技，选自己最容易写对的那个方案。这个道理我是在吃了好几次"为了快而写复杂，结果 debug 半天"的亏之后才真正懂的。

2. 暴力回溯的完整实现：先把正确性锁死

无论最终决定用哪种算法，我都建议先写一版暴力回溯把答案跑对。这不是浪费时间，而是给自己留一条安全绳：万一后面那个看似聪明的贪心证明有漏洞，你手里还有个绝对正确的程序可以用来对拍验证。这道题的候选集极小，暴力回溯本身就能直接通过很多数据范围，所以这套代码也不完全是"过渡产物"。

回溯的写法非常模板化，从大到小尝试每个候选阶乘，每个候选有"用"和"不用"两个分支，递归到终点判断累计和是否等于目标值。下面是我用 C++ 写的一版，加了后缀和剪枝，跑起来飞快：

#include <bits/stdc++.h> using namespace std; long long fact[20]; long long suffix[20]; // suffix[i] = fact[0] + fact[1] + ... + fact[i] bool dfs(int idx, long long cur, long long target, vector<int>& path) { if (cur == target) return true; if (cur > target || idx < 0) return false; if (cur + suffix[idx] < target) return false; // 剩下全加也不够 // 分支一：选用第 idx 个阶乘 path.push_back(idx); if (dfs(idx - 1, cur + fact[idx], target, path)) return true; path.pop_back(); // 分支二：不用第 idx 个阶乘 if (dfs(idx - 1, cur, target, path)) return true; return false; } int main() { fact[0] = 1; for (int i = 1; i < 20; i++) fact[i] = fact[i - 1] * i; suffix[0] = fact[0]; for (int i = 1; i < 20; i++) suffix[i] = suffix[i - 1] + fact[i]; long long n; cin >> n; int top = 0; while (top < 19 && fact[top + 1] <= n) top++; vector<int> path; if (dfs(top, 0, n, path)) { // path 是从大到小压进去的，反过来输出就是升序 for (int i = (int)path.size() - 1; i >= 0; i--) { cout << path[i] << "! "; } cout << "\n"; } else { cout << "impossible\n"; } return 0; }

几个实现细节值得单独说。第一，suffix 数组存的是前缀和，用于"剩余全选也不够"的剪枝，这个剪枝在目标值比较小的时候效果极其明显，能把实际遍历量从指数级压成接近线性。第二，top 的寻找有讲究，我用 fact[top + 1] <= n 的方式一边找一边防止数组越界——这个坑后面单独展开。第三，路径 path 存的是阶乘下标，输出时要按下标对应输出 i! 而不是直接输出 fact[i]，因为题目要的是"哪几个阶乘"而不是"加起来等于多少"；又因为递归是从大到小推入 path 的，最后要倒序输出才是升序。

2.1 为什么"先写暴力"不是浪费时间

我见过很多选手，包括以前的我自己，一上来就直奔最优解，觉得写暴力是耻辱。但在这道题上，暴力版至少有三个不可替代的作用。第一，它是你验证贪心正确性的裁判——随机生成几千个 n，暴力版和贪心版对拍，结果完全一致你才敢提交；第二，它是你理解题意的工具，写暴力逼你把约束想清楚，比如 0! 和 1! 到底算不算两个独立项，这种问题不实际跑一遍你根本察觉不到；第三，它是你心理上的保底，哪怕比赛中途贪心写挂了，你也能快速退回暴力拿分，而不是在空编辑器前面大脑一片空白。

说实话，我见过太多人"优化版本写挂了，暴力版本又没留"，最后整题送掉。先暴力后优化，这不是保守，这是工程习惯。暴力代码虽然看起来"笨"，但它是你整个解题过程中唯一可以百分之百信赖的参照物，这笔账怎么算都划算。

2.2 分支顺序决定回溯的实际开销

在"用"和"不用"之间，我选择先走"用"的分支。原因是：先用当前最大的阶乘，能更快把 cur 顶到接近 target 的位置，配合后缀和剪枝，大量分支会在两到三层之内被判定为"不可能"，直接砍掉。反过来，如果你先走"不用"的分支，前几层都会沿着"啥也不选"的路径往下深入，剪枝逻辑完全发挥不出来，实际遍历次数能差出几个数量级。

我自己实测过一个例子，n 取 119（= 5! - 1，一个特别"恶心"的值），"先用后不用"的顺序加上剪枝，递归调用次数是几百次；反过来跑，直接膨胀到几十万次。同样的题目，同样的答案，只因为分支顺序不同，性能差出千倍，这就是细节的力量。以后你写任何子集类回溯，都建议把"能选就先选"这个原则焊死在脑子里。

3. 贪心解法：为什么从大到小直接取就是对的

暴力能过是一回事，但要是你真觉得这题就这么完了，你就漏掉了出题人最想让你看到的东西。这道题的隐藏主线，是贪心——从不超过当前剩余值的最大阶乘开始，能取就取，然后让剩余值继续循环，直到归零或者卡住。这个算法连复杂的数据结构都用不上，时间复杂度 O(候选个数)，几乎可以当作 O(1) 看待。

但贪心算法最忌讳的就是"看着对"。你必须先证明：每一步取当前能取的最大阶乘，不会把后面带进死胡同。这道题的证明核心是一条不等式：任意若干个比 i! 小的阶乘之和，严格小于 i!。换句话说，1! + 2! + ... + (i-1)! < i!。一旦这个不等式成立，贪心的每一步其实都没有第二选择：如果当前剩余值 r >= i!，不选 i! 的话，剩下的所有项加起来都够不到 i!，更够不到 r，所以 i! 必须被选；如果 r < i!，选了它就直接超了，一定不能选。两种情况都只有唯一解，贪心自然就是最优。

3.1 归纳法的完整推理，别跳过

我来把这个不等式完整推一遍，保证你看完能自己复述。要证：对任意 i >= 1，sum_{j=1}^{i-1} j! < i!。

先看 i = 2：左边是 1! = 1，右边是 2! = 2，成立。假设结论对 i 成立，即 sum_{j=1}^{i-1} j! < i!，那么对于 i + 1：

sum_{j=1}^{i} j! = (sum_{j=1}^{i-1} j!) + i! < i! + i! = 2 * i! < (i+1) * i! = (i+1)!。

最后一步用到了 i + 1 > 2，对 i >= 2 成立，而 i = 1 的情况可以直接验证：左边是空集求和 0，右边是 1! = 1，0 < 1 成立。所以归纳成立，结论对一切 i 都成立。

这个证明看起来就五行，但它是整道题从"赌"变成"算"的分水岭。我建议你合上文章自己写一遍，写不出来的地方就是你还不够懂的地方。比赛时真正卡住你的往往不是"会不会写"，而是"敢不敢用"——只有你自己推过一遍，提交时手才不抖。

3.2 0! 和 1! 撞值：贪心最怕的就是值重复

现在回到坑王：0! = 1! = 1。如果题目说"不同非负整数的阶乘"，那 0 和 1 是两个不同的下标，值却都是 1，贪心到这里就要纠结：剩余值是 1 的时候，到底选 0! 还是选 1!？答案是都行，它俩对"和"的贡献完全一样，只影响你输出时的下标。但有个更隐蔽的情况：如果目标值是 2，方案是 1! + 0!，这时 0! 和 1! 被同时使用了，这在"不同下标"的约束下是合法的。如果你在实现里只保留一份值为 1 的阶乘，这个用例直接算不出来。

我拿到的题目版本里，有的明确说候选从 1! 开始，有的没说，有的干脆规定 0! 和 1! 等价。遇到这种情况，我的建议是：看题面有没有把 0! 列进候选，如果列了，就要处理"值为 1 的项可以承担两次选择"这个特殊情况；如果没列，就当作只有一份 1。实在不确定，就在对拍阶段把两个版本都跑一遍，哪个能过样例就用哪个——这不是投机，这是在信息不全的情况下最稳妥的工程决策。尤其是对拍时多生成几个值为 1 和 2 的小用例，这两个数能最快暴露你对 0! 的处理是否到位。

4. 实测踩过的坑：溢出、剪枝和评测格式

下面这部分是我真实做题时浪费过最多时间的三个地方，每一个都值得你提前打预防针。这些坑的共同特点是：不跑到边界你根本察觉不到，一跑到边界就直接 WA 或者 RE（运行错误），而且报错信息往往还含含糊糊，让你根本不知道错在哪一行。

4.1 阶乘数组的溢出，防不胜防

20! = 2432902008176640000，这个值恰好还在 long long 的范围内，但 21! = 51090942171709440000 已经炸了。所以如果你开 fact[20]，下标只能用到 19。问题出在寻找 top 的循环上：如果 n 很大，比如 10^18，fact[top + 1] <= n 会让 top 一路涨到 19 之后还想继续涨，再去访问 fact[20] 就是越界读垃圾值，输出一个完全没法看的负数或者随机值。

我当时就是没给 top 加上限，本地测小数据全对，一测大 n 就崩。修正起来很简单，循环条件加一个 top < 19 就完事。但更值得记的教训是：凡是写"递增寻找上界"这种循环，一定要问自己一句，这个上界如果不存在，我的循环会不会越界。类似的场景还有二分查找的左右指针、模拟走棋盘的步数计数器，都是同一个道理——防御性编程省下的 debug 时间，远比多写两行条件判断的成本高。

4.2 后缀和剪枝不是可有可无的优化

有人觉得这题候选只有十几个，剪不剪无所谓。大错特错。没有后缀和剪枝的纯回溯，在最坏情况下会遍历一个非常混乱的子集树，我实测 n 在 10^8 附近的输入，纯回溯要跑好几秒，加了剪枝之后是毫秒级。差距不是常数级的，是数量级的。

剪枝的思路很简单：如果当前累加值 cur 加上"剩下所有还能选的阶乘之和"都小于 target，那这个分支无论怎么走都救不回来，直接返回 false。这行代码在各种子集类题目里都通用，建议当成肌肉记忆写进你的回溯模板。另外提醒一句，suffix 数组本身也要用 long long 存，因为阶乘值本身就可能很大，用 int 存前缀和又埋一个雷。

4.3 输出格式能让你挂在最后一米

构造方案类题目，算法全对、输出格式不对照样不给分。有的题目要求按下标升序输出，有的要求按阶乘值升序输出，有的要求输出"3! + 2! = 8"这种带表达式的格式。我在"3! + 2!"和"3!+2!"之间因为少了一个空格，被判过一次格式错误，那种感觉比算法错误还憋屈。

应对方法特别笨但特别有效：把样例输出下载下来，逐字符比对，包括空格、感叹号、换行。别嫌低级，这种分丢得最冤。另外，如果你的程序在有多组答案时输出的是其中一组，而评测只校验正确性，那没问题；但如果要求输出字典序最小或下标最小的方案，你就得在 dfs 的分支顺序上做文章——通常优先选小下标就能保证字典序最小，这又是一处容易忽略的隐藏要求。

5. 从阶乘和看出去：这类"大数小候选"问题的通用套路

做完整道题你会发现，真正能带走的东西不是这段代码，而是一个方法论：遇到数值增长极快的序列，先截断候选集，再考虑搜索或贪心。这套思路可以迁移到一大批题目上，下面展开说说。

5.1 顺带认识一下阶乘数字系统

如果不是要求"每个阶乘最多用一次"，而是允许加权——第 i 个阶乘前面的系数可以取 0 到 i——那就是阶乘数字系统（factoradic），任意非负整数在这个系统里都有唯一表示。比如 10 可以写成 1×3! + 2×2! + 0×1! + 0×0! = 6 + 4 = 10。这个系统和排列的字典序编号有直接关系，康托展开本质上就是它。本题"系数只能取 0 或 1"是它的一个特例，理解了这两者的区别，你以后看到"系数带范围"的题就不容易混。

说个小发现：factoradic 和二进制特别像。二进制是每位系数 0 或 1、位权 2^i；factoradic 是每位系数 0 到 i、位权 i!。两者唯一性的来源是同一个数学事实——低位权的总和超不过向高位的进位最小值。这个观察让我后来看很多数论题都通透了不少，推荐你也试着用这种"找共性"的方式去总结做过的题。

5.2 一张表帮你识别同类题

以后看到下面这些特征，可以直接往"截断候选集 + 贪心/搜索"的路子上想：

你会发现，这些题的本质几乎一样：候选序列的增长速度足够快，以至于"小项之和永远追不上大项"，于是贪心天然正确。看懂这一层，你就不需要背题解了。看到新题时先问一句"候选序列的增长速度到底有多快"，这个习惯能让你少走很多弯路。

6. 送给同样在刷题的你的几条实战建议

最后分享几个用真金白银换来的习惯，希望你不用像我一样踩完坑才记住。

6.1 提交前的自检清单

我给自己定了一个固定流程：代码写完后，先跑六类边界用例——0、1、2、恰好等于某个阶乘的数、比最大可表示阶乘大 1 的数、数据上限附近的数。这六类测完，这道题的基本盘就稳了。然后再随机生成几千个中等规模的数据，让暴力版和优化版对拍，验证优化没有破坏正确性。最后逐字符比对输出格式。这套流程看起来繁琐，但真能拦住绝大多数低级失误。

6.2 心态层面的建议

这道题说难不难，说简单又不简单。它真正考的，不是你会不会写阶乘，而是你对基础数学性质的敏感度——看到超指数增长能想到截断，看到"小和追不上大项"能想到贪心，看到 0! = 1! 能想到特判。这种敏感度是刷模板刷不出来的，只能一道题一道题慢慢磨。如果你正在准备比赛，我建议把从暴力到贪心的完整推导过程亲手写一遍，特别是那条归纳不等式，别看懂了就翻篇。

我自己的体会是，像"阶乘的和"这种题，最大的价值不是让你记住某个算法，而是让你在一次次"以为简单、实际有坑、最后想通"的循环里，建立起对题目的敬畏和对细节的敏感。希望这篇笔记能帮你少走几步我走过的弯路。