半数集问题在《算法分析与设计》这类课程的目录里通常排在 2.8 这个位置夹在递归与分治章节的中间。它的题干短得可怜两三条规则看着像一道小学找规律题可真正动手写代码的人会被它绊一下规则里那句不能超过最近添加的数的一半八成的人第一次都读错了对象算出来的集合元素少了一半然后对着参考答案怀疑人生。我当年也是这么栽的后来把它彻底拆开讲给几届学弟学妹听才算把这道题里所有该踩的坑都摸清了。这篇就按我自己啃它的顺序来规则到底怎么读、集合里那些数字串是怎么长出来的、递推式从哪冒出来的、三种写法分别该在什么场合用、以及那个和它长得几乎一样但结果不同的半数单集到底差在哪。不管你是刚学递归想找个练手题还是复习算法课准备笔试面试看完这一篇基本能自己推、自己写、自己验。1. 半数集到底在数什么三条规则翻译成一句人话1.1 不能超过最近添加数的一半约束的到底是谁教材原文大致是这样的给定自然数 n由 n 开始依次产生半数集 set(n) 中的数。(1) n 本身属于 set(n)(2) 在 n 的左边加上一个自然数要求这个自然数不超过最近添加的数的一半(3) 按此规则继续处理直到不能再往左加为止。这三句话里最容易读错的就是最近添加的数。很多人第一反应是n 的一半于是算出 set(6) {6, 16, 26, 36}四个数然后发现标准答案有六个怎么都对不上。正确的理解是每次新加的数都贴在当前整个数字串的最左边而最近添加的数指的是上一次贴上去的那个数也就是现在位于最左边的那个。所以真正的约束是新加的数 ≤ 上一次加的数的一半而不是≤ n 的一半。第一次加的时候还没有上一次此时把 n 本身当作参照于是第一次加的数不超过 n 的一半。这个区别看着小影响的却是整条递归链。把参照对象锁定在最左边那个数之后你会发现整个构造过程是一路向左、数值一路递减的n 最大往左越来越小而且是每步至少砍一半。这就是它能被递归描述的根本原因。1.2 手推 set(6)六个数字串是怎么长出来的拿 n 6 手动走一遍比背十遍定义都管用。从 6 出发第一次能加的数不超过 6/2 3也就是 1、2、3 三个选择。选 1得到 16。现在最左边的数是 1能加的数不超过 1/2 0.5没有正整数可选停。产出 16。 选 2得到 26。最左边的数是 2能加的数不超过 2/2 1只能加 1得到 126。126 最左边的数是 1再加不了停。产出 26、126。 选 3得到 36。最左边是 3能加的数不超过 3/2 1.5取整数只能加 1得到 136。停。产出 36、136。再加上 6 本身set(6) {6, 16, 26, 126, 36, 136}一共六个和标准答案对上。再拿 n 8 练一遍手会更清楚每个分支后面挂着一整个子树这件事。8 的一半是 4第一次能加 1、2、3、4加 1 得 18停止加 2 得 2828 左边还能加不超过 1 的数得 128加 3 得 38还能加不超过 1 的数得 138加 4 得 484 的一半是 2可以加 1 或 2加 1 得 148加 2 得 248而 248 左边还能加不超过 1 的数得 1248。连上 8 本身set(8) 一共十个元素8、18、28、128、38、138、48、148、248、1248。注意 248 这一支它来自48 再加 2而 2 又是4 的一半允许的范围。这条链是 8 → 48 → 248 → 1248每一步左边的数都至少是右边那个数的一半规则始终成立。1.3 为什么这个构造天生就是递归结构观察 set(8) 里以 4 开头的那些元素48、148、248、1248。把这四个数字串各自去掉最右边的 8剩下 4、14、24、124——这恰好就是 set(4)。再看以 2 开头的28、128去掉末尾的 8 剩下 2、12正好是 set(2)。这不是巧合而是构造规则决定的必然结果。整个集合可以这样描述set(n) { n } ∪ { 把 s 拼在 n 左边 : 1 ≤ i ≤ n/2, s ∈ set(i) }用人话说就是要么就是 n 自己要么先选一个不超过 n/2 的数 i 贴到 n 左边剩下的部分就是 set(i) 里任意一个元素再往左延伸的结果。这条等式把数一个集合有多少元素直接变成把若干个小规模同类问题的答案加起来递归的骨架就这么立起来了。2. 为什么照规则生成会撞墙朴素做法的三重代价2.1 用集合容器存字符串能撑到多大最直观的写法是照着规则老老实实地生成用 C 的 set 或者 Python 的 set从 { str(n) } 出发对每个候选数 i 递归生成 set(i)再把 i 拼到每个元素前面塞进去。这个写法在小数据下完全正确跑 n 20 秒出结果但你试着把 n 提到 30 往上就会发现不对劲内存涨得飞快时间更是断崖式上升。问题出在两点。一是同一个数字串会被生成很多次集合容器虽然能帮你去重但去重之前的那次拼接和插入的开销是实打实付出去的。二是数字串本身很长n 越大串越长字符串拼接和哈希的开销成正比缓存也扛不住。如果你只是想验证自己对规则的理解有没有偏差这个写法是很好的标尺但千万别拿它交作业。2.2 同一批子问题被重复算了多少次真正致命的是重复子问题。回到 set(6) 的例子计算 set(6) 需要 set(1)、set(2)、set(3)而 set(4) 需要 set(1)、set(2)set(3) 又需要 set(1)。也就是说 set(1) 在整个过程中被反复调用。朴素递归调用的次数增长得比结果本身还快。你可以自己加个计数器试试n 30 的时候f(1) 会被调用上万次而它每次返回的都是同一个 1。这就是典型的做了大量重复功和教材里讲斐波那契数列朴素递归的问题一模一样。半数集问题被安排在递归那一章用意也在这里先用一个规则好懂、结构清晰的题让你亲眼看到朴素递归为什么慢然后自然过渡到记忆化。2.3 记忆化的第一性原理算过的就存下来记忆化memoization的核心只有一句话如果一个函数的返回值只由参数决定那同一个参数算过一次就够了把结果记在本子上下次直接查。半数集问题完美符合这个前提。f(n) 只由 n 决定不受调用路径影响也不会随时间变化。所以开一个数组 memo初始化为 0每次进入函数先查表表里有值就返回没有就老老实实算算完顺手写回表里。改完之后你会发现n 从 30 提到 1000运行时间几乎是线性的因为每个 f(n) 最多被真正计算一次。这个改动通常不超过五行代码收益却是数量级的。有一个细节值得单独说memo 数组别用 0 当未计算的标记因为某些问题的合法返回值可能真是 0。半数集里 f(n) 恒大于 0用 0 当哨兵是安全的。但换成别的题比如问方案数为 0 的情况就得额外开一个 visited 数组。这是个通用的习惯问题写多了会自然形成肌肉记忆。3. 递推式 f(n)1Σf(i) 的推导与两个关键边界3.1 按第一次加的数做分类计数从 1.3 那条等式出发数元素个数就很简单了。set(n) 里的元素分两类一类是 n 自己贡献 1 个另一类是先加了某个 i再往左延伸的所有结果。对于固定的 i这些结果的数量等于 set(i) 的元素个数也就是 f(i)。而 i 的取值是从 1 到 ⌊n/2⌋。两类加起来f(n) 1 Σ (i 从 1 到 ⌊n/2⌋) f(i)且 f(1) 1验证一下f(2) 1 f(1) 2f(3) 1 f(1) 2f(4) 1 f(1) f(2) 4f(5) 1 f(1) f(2) 4f(6) 1 f(1) f(2) f(3) 6。全部和手推结果一致。把这个分类思路说透一点为什么按第一次加的数分类是不重不漏的因为每个非 n 的元素它最左边的那个数一定是某一步加进去的而构造过程从右往左是唯一的所以第一次加的数是谁这个标签对每个元素都是唯一确定的。分类不重不漏加法原理才能直接用。3.2 上界取 ⌊n/2⌋ 时的取整细节递推式里那个 ⌊n/2⌋ 是整数除法向下取整不是四舍五入也不是向上取整。n 6 时上界是 3n 7 时上界还是 3因为 7/2 3.5取整后是 3。这件事在代码里不用特别处理因为 C、C、Java 里两个正整数相除本来就是向下取整。但在 Python 里要留个心眼Python 的 // 对正整数也是向下取整没问题只有涉及负数时行为才和 C 系不同。半数集里 n 恒为正所以 n // 2 直接可用。顺带一个观察因为上界是向下取整f(2k) 和 f(2k1) 的值其实相等。n 2k 和 n 2k1 的求和上界都是 k所以 f(2k1) f(2k)。手推数据也印证了这点f(2) f(3) 2f(4) f(5) 4f(6) f(7) 6f(8) f(9) 10。这个性质在做题时可以用来快速核对也可以用来做小优化。3.3 f(1)1 这个锚点为什么不能改成 f(0)1递归必须有出口。半数集里最自然的锚点是 f(1) 1数字 1 往左加不了任何数因为 1/2 向下取整是 0可选范围为空集合里只有它自己一个元素。有人会图省事把出口设成 f(0) 1理由是什么都不加也是一种然后对所有的 n 都用同一个求和循环。这个改法在数值上有时能凑出正确结果但逻辑上是错的f(0) 对应的是从 0 出发的半数集而半数集问题里 n 是自然数0 并不在定义域内。把它当锚点等于偷偷引入了一个定义外的状态一旦题目加个约束比如要求 n ≥ 1 且统计空集不计数结果立刻就跑偏。另一个常见的坑是把锚点写成 f(1) 1 之后循环上界写成 n/2 却忘了处理 n 1 的情况。此时 n/2 0循环一次都不进返回值 1恰好正确所以肉眼不容易发现。但如果哪天把返回初值写成 0就会静默出错。写递归时把出口单独放在函数最前面是个值得坚持的习惯。4. 三种实现路线朴素递归、记忆化搜索、自底向上打表4.1 朴素递归版本短小但只能跑到小数据先把最原始的版本写出来它的最大价值是当作对照物long long half(int n) { if (n 1) return 1; long long sum 1; for (int i 1; i n / 2; i) sum half(i); return sum; }这段代码六行逻辑和递推式一一对应可读性极好。用它能轻松算出 f(1) 到 f(30) 的所有值用来和手推结果对答案非常方便。代价是重复计算。调用 half(30) 会递归调用 half(15)、half(14)……而 half(15) 又会调用 half(7)、half(6)……同一批参数被反复穿透。实际跑一下就知道n 35 左右它就开始明显卡顿n 40 基本等不到结果。这不是机器差是算法的调用次数按指数涨。4.2 记忆化版本改动不超过五行效果立竿见影在朴素版本上加一个备忘录数组long long memo[1005]; long long half(int n) { if (n 1) return 1; if (memo[n] ! 0) return memo[n]; long long sum 1; for (int i 1; i n / 2; i) sum half(i); return memo[n] sum; }进了函数先查表查到了直接返回查不到就算算完写回。就这四处改动n 从 35 提到 1000 都能瞬间出结果。为什么效果这么夸张因为每个 f(n) 最多被真正计算一次剩下所有调用都在查表。总的实际计算量等于 n 的大小再加上每次循环枚举 i 的开销。整体复杂度降到 O(n²) 量级n 1000 也就是百万次基本操作眨眼就完。有一个小地方要注意全局数组默认清零正好可以当未计算标记。如果放在函数里用局部数组一定要记得显式初始化否则读到的是栈上的垃圾值会得到诡异的结果。4.3 自底向上版本多组询问场景下的性价比之王如果是笔试或者在线评测题目里给一堆查询每个查询给一个 n 问 f(n)那更合适的做法是一次性把所有答案打出来const int N 1005; long long dp[N]; void build() { dp[1] 1; for (int i 2; i N - 1; i) { long long s 1; for (int j 1; j i / 2; j) s dp[j]; dp[i] s; } }外层从小到大枚举 i内层把 1 到 i/2 的答案加起来。因为算 dp[i] 的时候所有比 i 小的值都已经算好了随便取。预处理一次之后每次查询 O(1)。用 Python 写同样清爽N 1005 dp [0] * N dp[1] 1 for i in range(2, N): dp[i] 1 sum(dp[1:i // 2 1])这里有个可以顺手做的优化求和部分可以用前缀和数组代替。定义 pre[i] dp[1] dp[2] ... dp[i]那么 dp[i] 1 pre[i // 2]。维护前缀和是 O(1) 的整个预处理就从 O(n²) 降到 O(n)。n 不大时两种写法差别看不出但一旦 n 上到十万级别前缀和就是必须的。4.4 拿生成法给递推法做对拍写了三种实现怎么确认它们都对最稳的办法是写一个笨但绝对正确的生成法和递推结果逐个比对def gen(n): res {str(n)} for i in range(1, n // 2 1): for s in gen(i): res.add(s str(n)) return res def half(n): if n 1: return 1 return 1 sum(half(i) for i in range(1, n // 2 1)) for n in range(1, 16): assert len(gen(n)) half(n), ngen(n) 严格按规则拼接字符串用集合去重逻辑上无懈可击。跑一遍 1 到 15 全部通过说明递推式推导没毛病后面的记忆化、自底向上只是同一公式的不同写法自然也一起被验证了。这个先造标尺再对拍的习惯我从做课程作业时就养成了后来刷题、写业务代码都在用。花十分钟写个笨办法能省掉后面几小时的怀疑。5. 跑通之后才踩的坑溢出、边界与查询方式5.1 结果的增长速度到底有多快半数集的答案增长不算爆炸但也绝对不快得可以忽略。手算几组数据心里就有数了n123456789102050100f(n)1224466101014607869828从表里能看出两点。一是 f(2k1) f(2k)成对相等前面已经解释过原因。二是增长明显快于线性n 从 50 到 100结果从 786 涨到 9828涨了十几倍。用 long long64 位有符号整数上限约 9.2×10^18承载在常见的课程数据范围n 一般不超过几百内是足够的。但如果你把 n 开到很大或者题目本身对精度有要求就得换成大整数或者用数组模拟十进制加法。判断标准很简单先把纯递推跑一遍打印中间值看看有没有突然变成负数一旦出现负值就是溢出了别犹豫上高精度。5.2 多组输入时别每次都从头算在线评测里常见两种输入格式。一种是单组读一个 n 输出一个数怎么写都行。另一种是第一行给一个 T后面跟 T 个查询这时候如果每个查询都从头递归纯属浪费。正确姿势是先把 1 到最大可能的 n 全部预处理到 dp 数组里然后每个查询直接查表输出。预处理只做一次T 次查询全是 O(1)总复杂度从 O(T·n²) 降到 O(n² T)。还有一个隐形陷阱如果题目给了 n 的范围是 1 到 10^5但你没读题就开了个 1005 的数组越界访问可能不报错直接读到相邻内存里的垃圾值输出一个看起来很合理的错误数字。这种错误最难查因为程序不崩。养成先看数据范围再定数组大小的习惯能躲开一大半这类问题。5.3 边界输入的处理清单实际提交前我会固定跑这几个边界值n 1应该输出 1验证递归出口n 2应该输出 2验证上界为 1 时循环能进n 3应该输出 2验证和 n 2 结果相同n 取题目给出的最大值验证数组够大、不溢出如果是多组输入再补一个 T 组全是同一个值的用例验证查表逻辑。这几条覆盖了出口、取整、成对相等、容量、查询这五类最容易出问题的地方。十来分钟就能跑完比事后花几小时 debug 划算得多。6. 顺带说清一个孪生问题半数单集的去重逻辑6.1 定义只多了一句元素互异结果就变了教材在讲完半数集之后往往会跟一个半数单集问题生成规则和半数集一模一样唯一的区别是要求 set(n) 中的元素互不相同统计的是去重之后的不同元素个数。第一次看到这段会觉得莫名其妙规则里每一步的取值范围都是限定的加进去的数怎么可能重复但把 n 取大一点真去生成一遍就会发现确实会撞。问题的根源在于集合里的元素是十进制拼接出来的数字串而拼接本身是有歧义的。同一个数字串可能被两条不同的构造路径产生出来。6.2 重复从哪来1224 的两种拼法拿 n 24 举例把注意力放在元素 1224 上。路径一第一步加 1212 不超过 24/2 12合法直接得到 12 拼 24 就是 1224结束。 路径二第一步加 22 不超过 12合法得到 224第二步往左加 11 不超过 2/2 1合法得到 1 拼 224也就是 1224。两条路径产出的数字串一模一样都是 1224。在按递推式 f(n) 1 Σf(i) 计数时i 12 这一支算了一次i 2 那一支的子树里又算了一次同一个元素被登记了两遍。这就是重复的来源当某个加数是两位数或更多位时它有可能被拆成两个更小的数分别贴在相邻的两步里而两步都满足减半约束。6.3 小范围直接去重最稳大范围才需要考虑优化知道了原因处理方法就清楚了。如果你的 n 不大比如不超过二三十最省心的做法就是照规则把数字串全生成出来扔进 set 去重最后输出集合大小。这段代码逻辑上不可能错跑得也快用来验证自己推导的判重规则是否严密是很好的工具。如果 n 给得大全量生成不现实就得把重复的数量解析地算出来在递推式里减去。这一步的推导要处理某个加数能否被合法拆分这类条件细节比半数集本身复杂不少不同教材给出的表达形式也不完全一样。我自己的经验是先写小范围的全量去重版本拿它在 1 到 30 上打出一张表再拿自己推的公式去对对上了再放到大数据上跑。直接上公式、跳过验证环节几乎一定会栽在某个边界上。顺带提一句半数集问题还常被拿来和整数划分做对比。整数划分是把 n 拆成若干个正整数之和顺序不计半数集是往左贴数字每个数字串的构造顺序是唯一的。两者都是把大问题拆成小问题再合并但拆法的约束和计数对象完全不同写代码时千万别把两套递推式混着用。最后分享一个我自己做题时的小习惯每碰到一个像半数集这样的递推题我都会先手推三到四组小数据把它们列成一张表贴在草稿纸边上然后推导公式用这张表验证最后写代码再用代码生成的表去覆盖手推的那张。三张表能对上这道题才算真的过关。这个流程对付递归分治这一章的题屡试不爽。