1. 半数集到底在数什么定义拆解与递推公式的自然推导教材里把半数集问题放在递归与分治这一章但很多人第一次看到题目时会想这不就是个递归枚举吗为什么还要专门作为一节来讲我先说一个容易被自己骗过去的点半数集的生成规则不是“每次都能在原数左边加任意一个不超过原数一半的数”而是“加完之后新的数作为下一次的限制数”。这两个说法看起来差不多实际差别很大。题目典型描述是给定一个自然数n由n开始可以依次产生半数集set(n)中的数。n本身是set(n)中的元素在n的左边加上一个自然数但这个自然数不能超过“最近添加的数”的一半按这个规则继续处理直到不能再加为止。注意关键是“最近添加的数”。第一次加时最近添加的数就是n所以设n6左边能加的是1、2、3。得到16、26、36。接下来以26为例最近添加的数是22的一半是1所以还可以在26左边加一个1得到126以36为例最近添加的数是33的一半取整是1所以可以加一个1得到136而16中最近添加的数是11的一半取整是0就停住了。因此set(6)最终是{6, 16, 26, 36, 126, 136}一共6个元素。我把这个规则翻译成递推式。令f(n)表示以n为起点生成的半数集大小那么除了n自身这一项所有在n左边加了i1 ≤ i ≤ n/2的情况剩下的操作等价于“以i为新的起点”继续生成数量恰好是f(i)。所以f(n) 1 f(1) f(2) ... f(⌊n/2⌋)当n1时⌊1/2⌋0右边只有1所以f(1)1。这个式子不是猜的它完全对应生成过程先固定最右边的原始数字n第一次加的数i决定了后续所有扩展而不同i生成出的数字串最左边数字不同不会相互混淆因此可以放心相加。从组合结构上看半数集里的每一个数字串从右往左看其实是一串限制数n然后第一次加的数第二次加的数……这些数满足一个非常强的性质后一个数不超过前一个数的一半。也就是说每往左走一步数字规模至少要减半一次。这意味着无论n多大单个数字串的长度最多只有⌊log2 n⌋1这么长。这个观察在后面很有用递归深度不会爆炸真正爆炸的是没有缓存的重复计算。2. 朴素递归的重复账本调用次数为什么恰好等于结果数先写一个最直接的递归版本几乎所有第一次接触这道题的人都会写出来def half_set_count(n): total 1 for i in range(1, n // 2 1): total half_set_count(i) return total这个代码逻辑完全正确跑n6得到6跑n10得到14看起来没什么问题。但如果你在函数里加一个计数器会发现一件很有意思的事计算f(10)的过程中f(1)被调用了很多次f(2)也被调用了很多次f(3)、f(4)同样如此。为什么会重复因为f(n)的定义是“把从1到n/2的所有f(i)全部加一遍”这意味着f(10)会调用f(1)到f(5)f(5)又会调用f(1)和f(2)f(4)也会调用f(1)和f(2)于是f(1)、f(2)被反复计算。这是典型的子问题重叠同一个f(i)在计算不同父问题的时候都会被重新算一遍。我一开始也没意识到这个重复到底有多严重直到把调用次数算出来。设T(n)为计算f(n)时函数总调用次数包括最初进入的那一次则有T(n) 1 T(1) T(2) ... T(⌊n/2⌋)这个递推式和f(n)的定义式长得一模一样初始情况T(1)1也等于f(1)所以直接得到结论朴素递归的调用次数恰好等于半数集的元素个数。这不是巧合而是因为每次计算都要重新遍历一遍所有子问题工作量正好对应着最终计数结果。我递归算了一组值简单列在下面n1234568101214161820242830f(n)1224461014202636466094140166n30时调用次数166次确实不大。但注意这个数列的增长趋势n从16涨到30差不多翻了一倍结果从36涨到166涨了4倍多。等n到100调用次数会上涨到很夸张的量级。很多教材说它“指数级增长”不算严谨但说“重复计算量随n快速膨胀”是完全没有问题的。更重要的是这种重复是可以直接从定义式里预判的光靠“加个n100试试”这种思路去解决问题迟早会在更大的数据上吃亏。3. 线性做法记忆化与带前缀和的递推实现既然重复是因为同一个子问题被反复计算最容易想到的修复方式就是记下来。用一张表把算过的f(i)存起来下次遇到直接取这就是记忆化递归。def half_set_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] total 1 for i in range(1, n // 2 1): total half_set_memo(i, memo) memo[n] total return total每个f(i)只会被真正计算一次所以总状态数是O(n)每个状态内部还要做一次循环相加总复杂度可以粗略看作O(n^2)量级。这个写法已经能应付大多数题目但还可以继续优化。关键在于递推式本身。如果维护一个前缀和数组pref[k] f(1) f(2) ... f(k)那么f(n)可以写成f(n) 1 pref(⌊n/2⌋)而前缀和可以随着递推同步更新pref[i] pref[i-1] f[i]。这样每个f(i)用O(1)时间算出来整体复杂度降到O(n)空间O(n)。这个思路适合多组输入的题目一次算到最大n后面每个查询都是O(1)查表。def half_set_dp(max_n): f [0] * (max_n 1) pref [0] * (max_n 1) for i in range(1, max_n 1): f[i] 1 pref[i // 2] pref[i] pref[i - 1] f[i] return f, pref注意i1时pref[0]正好是0所以f[1]1不需要单独写分支。这个实现短得有点不像递归题的解但它背后的优化思想值得记住当递推式依赖一段前缀和时别傻傻地每次都重新累加维护一个running sum通常能省掉一个维度。用C写的时候要稍微小心#include vector using namespace std; long long halfSetDP(int n) { vectorlong long f(n 1, 0), pref(n 1, 0); for (int i 1; i n; i) { f[i] 1 pref[i / 2]; pref[i] pref[i - 1] f[i]; } return f[n]; }为什么用long long因为f的增长比线性快得多到n1000时可能就超出int的范围了。具体什么时候溢出取决于平台int是32位还是更长稳妥起见直接用long long再大就考虑取模或大整数。4. 要输出全部数字怎么办DFS生成与去重变体计数问题往往是“按个数问”但有些题目会要求把set(n)里的数字全部打印出来。这时候递推计数就不再够用得改成真正的生成算法。DFS的写法不复杂关键是把“当前限制数”作为状态传下去。初始状态限制数是n每次尝试在左边加一个1到⌊limit/2⌋之间的数加完后新的限制数变成刚加的那个数。def dfs(limit, cur, result): result.append(cur) for i in range(1, limit // 2 1): dfs(i, str(i) cur, result) result [] dfs(6, 6, result) print(result) # [6, 16, 26, 126, 136, 36]注意这里用字符串拼接而不是真正做整数拼接原因很简单n比较大的时候比如n10000数字串“110000”转成整数再转换回来既容易错又没有必要用字符串天然避免数值溢出。字符串拼接的开销在绝大多数题目里也不是瓶颈。跑一下n6会得到上面那一串结果顺序和教材手工推的略有差异但集合内容一致。这里也顺便验证了第1节对定义的理解16之后不能再加26之后只能加136之后只能加1最终集合就是6个元素。如果题目变成“半数单集”含义往往是要求统计时去掉重复元素。按照我前面分析的生成规则同一个固定n下不同添加序列对应不同数字串理论上不会出现重复。但OJ或教材版本之间对“半数集”的定义措辞并不完全统一有的版本会把“最近添加的数”理解成“当前整个数字串”这时集合里就会出现重复。碰到这类不太确定定义的题最稳妥的做法是用set收集结果生成一遍再去重牺牲一点时间换正确性def half_set_set(n): s set() def dfs(limit, cur): s.add(cur) for i in range(1, limit // 2 1): dfs(i, str(i) cur) dfs(n, str(n)) return len(s)n ≤ 30的时候这个做法完全可行。如果想进一步优化再根据去重后的规律推导递推式但我的经验是先跑通暴力版本拿小数据验证理解是否正确再考虑数学优化顺序不能反。5. 边界、溢出与实战中容易写错的细节最后一个部分聊几个容易踩的坑。这些坑在书上的例题里不明显但放到考试、面试或者OJ上一个不注意就会导致答案错误或者代码超时。第一个坑是n0和n1。半数集问题通常默认n是正整数但万一输入给0要有一个明确的行为。如果按“0本身在集合中且没有更小的数可加”来理解那结果应该是1但某些题目的定义里半数集只针对正整数遇到0直接判输入非法。稳妥做法是在代码开头单独判断并和出题人给的样例对齐。第二个坑是递归深度。第1节已经说过单个数字串长度只有O(log n)所以DFS深度很小n10^9也不会爆栈不用为了这个问题手动改迭代。真正需要担心的不是深度而是无缓存时的时间复杂度。很多初学者把注意力放在“会不会超时”其实先想一想“同样的子问题算了多少遍”这个问题更本质。第三个坑是C的溢出。即使n只有几千f(n)也可能大得超出int的范围。老实说我一开始没意识到这点直到跑n1000时发现结果变成负数才开始查。建议比赛或作业里凡是这种增长明显超过线性的计数题一律先预估数量级能用long long就用long long必要时直接在递推过程中取模。取模不会有副作用因为递推式只有加法和查前缀和模运算完全兼容。第四个坑是状态设计错了。有人会把DFS的状态设计成“当前整个数字串”然后每次在左边加的数不超过“当前数字串的一半”。这会造成两个问题一是生成出来的数字串比实际半数集多得多二是递推关系变得混乱很难写出干净的DP。我自己的习惯是先问一句“这个状态里什么决定了下一步能加什么”答案就是最近添加的那个数也就是限制数。把限制数抽出来作为独立状态递推和DFS都会清楚很多。最后分享一点个人体会这道题放在“算法分析与设计”的递归章节真正的教学目的不是教你怎么数半数集而是让你建立两个习惯。第一个习惯是写出递归之后马上画一下调用树看看有多少重复节点第二个习惯是递推式里一旦出现对前一段的求和优先想到前缀和优化。这两个习惯在很多题里比单纯的AC更有价值。以后遇到变体比如限制数改成“不超过当前数三分之一”或者要求输出最大长度序列你只要抓住“限制数”这个核心状态就不会被表面的花样带偏。