集合划分问题是我接触C分治算法时遇到的一道很典型的题目。它的核心很简单把n个互不相同的元素分成k个非空集合问一共有多少种分法。这个问题的数学名字叫第二类斯特林数但比起背公式我更建议把它拆开看成一道分治题——每一次计算S(n,k)都依赖两个更小的问题S(n-1,k)和S(n-1,k-1)这正是“大事化小、小事化了”的典型过程。这篇文章我用集合划分这个例子把分治、递归、记忆化这条线完整串一遍并附上可以直接复用的C实现。适合正在学算法、准备面试或者想把分治思想练熟的朋友参考。1. 集合划分问题的本质递推公式就是分治的雏形1.1 问题定义与生活化理解先定义清楚问题有一个包含n个元素的集合例如{1, 2, 3, ..., n}要把这n个元素分配到k个集合中每个集合都必须非空且集合本身没有编号、没有顺序问有多少种不同的划分方式。这个数量就是第二类斯特林数记作S(n,k)。我第一次接触这个定义时最大的困惑在于“集合没有顺序”是什么意思。我换了个生活场景就理解了把n个朋友分成k个讨论小组每个小组至少有一个人。注意这里的小组没有编号谁在哪个组都行小组之间也不排序。举个例子n3、k2把{1,2,3}分成两个非空集合只有三种分法{1,2} | {3} {1,3} | {2} {2,3} | {1}如果把两个小组看成“有编号的”那还会多出三种对称的重复方案而斯特林数算的是无编号场景。这个区分非常关键后面写代码去重时就是围绕它做文章的。1.2 从递推式看“分而治之”第二类斯特林数有个经典的递推式S(n,k) k * S(n-1,k) S(n-1,k-1)这个式子怎么来的看第n号元素它只有两类归宿。第一类是加入已有的某个小组前n-1个元素已经分成了k组方案数是S(n-1,k)第n个元素可以插入这k组中的任意一组所以贡献k * S(n-1,k)。第二类是它自己单独成立一个新组前n-1个元素只需要分成k-1组方案数是S(n-1,k-1)。两类互不重叠加起来就是答案。递推式还需要配套边界条件我习惯整理成一张速查表条件S(n,k)的值原因n0, k01空集合分成0个非空子集视为一种合法情况n0, k00没有空集可塞元素非空子集数不可能是0kn0非空子集数量不可能超过元素总数k11所有元素放一个集合kn1每个元素单独一个集合这段理解为什么重要因为S(n,k)本质上是一个递归定义大问题依赖两个规模更小的子问题。看到这种结构第一反应就应该是分治算法和递归实现。2. 分治算法的视角为什么“拆分—求解—合并”在这道题上跑得通2.1 分治三步走对应到集合划分分治算法有一个通用模板分解、解决、合并。拿集合划分问题逐条对照分解计算S(n,k)时不要直接试图一口气算出答案而是拆成两个子问题——S(n-1,k)和S(n-1,k-1)。解决子问题的规模和参数都更小可以继续递归分解直到命中边界条件。合并把S(n-1,k)的结果乘上k再和S(n-1,k-1)相加就得到S(n,k)。我在写代码时会把这种思路写成伪代码形式函数 solve(n, k): 如果 n,k 命中边界条件直接返回对应值 否则返回 k * solve(n-1, k) solve(n-1, k-1)注意这个“乘k”和“相加”就是合并步骤。很多初学者只盯着递推公式忘了它本身就是分治思想的产物结果换个题型就认不出来。实际上你带着“分治三要素”去读任何递推式都会发现递推式就是分治的数学表达。2.2 递归树与重复子问题分治为什么需要记忆化如果单纯用分治递归写计算S(4,2)的调用关系大概长这样S(4,2) ├── 2 * S(3,2) │ ├── 2 * S(2,2) │ │ └── 返回 1 │ └── S(2,1) │ └── 返回 1 └── S(3,1) └── 返回 1表面上次数不多但把规模放大到n20时递归树会爆炸性增长。原因是同一个子问题被反复计算。比如S(2,1)在上面出现了两次而在更大规模的问题里S(5,2)、S(8,3)这类子问题会被各条递归路径重复访问几十次上百次。这就是分治的经典瓶颈分解出来的子问题往往高度重叠。解决办法是记忆化也就是把已经算过的S(n,k)存起来下次再遇到直接查表。到了这一步分治就自然地升级成了自顶向下的动态规划。我在实际刷题中最大的体会是分治负责提供“如何拆”的思维框架记忆化负责解决“拆完重复”的性能问题两者是一对天然搭档。3. C实现从纯递归到记忆化再到递推化简3.1 第一版干净但慢的纯递归先写一个最简单、最贴合递推公式的版本#include iostream using namespace std; long long stirling(int n, int k) { if (n 0 k 0) return 1; if (n 0 || k 0) return 0; if (k n) return 0; if (k 1 || k n) return 1; return k * stirling(n - 1, k) stirling(n - 1, k - 1); } int main() { cout stirling(10, 3) endl; return 0; }这段代码逻辑完全正确可读性也好但性能非常糟糕。最坏情况下它的时间复杂度是O(2^n)因为每个节点最多分叉两次树的深度是n。我试着跑了一下n20、k10等了很久都出不来结果n25基本就是天文数字的调用次数。所以这个版本只能用来对照理解公式不能真正投入工程使用。3.2 第二版加入记忆化的分治实现我加上一张备忘录表用二维vector来记录中间结果。关键点有两个一是memo的维度必须是(n1) * (k1)因为下标从0开始用二是初始值设为-1表示“还没算过”避免和合法的结果0混淆。#include iostream #include vector using namespace std; long long dfs(int n, int k, vectorvectorlong long memo) { if (n 0 k 0) return 1; if (n 0 || k 0 || k n) return 0; if (k 1 || k n) return 1; if (memo[n][k] ! -1) return memo[n][k]; memo[n][k] k * dfs(n - 1, k, memo) dfs(n - 1, k - 1, memo); return memo[n][k]; } long long stirling(int n, int k) { if (k n) return 0; vectorvectorlong long memo(n 1, vectorlong long(k 1, -1)); return dfs(n, k, memo); } int main() { cout stirling(20, 10) endl; return 0; }注意我在外层stirling函数里加了if (k n)的保护。这个判断看起来简单实际上避免了在dfs里访问memo时可能出现的一些逻辑混乱也让调用方不用关心非法参数。加上记忆化后时间复杂度降到O(nk)因为每个状态最多计算一次空间复杂度是O(nk)。n20、k10这类数据毫秒级出结果体感差别非常明显。3.3 第三版自底向上递推工程里的首选记忆化版本已经很好用了但工程上我更推荐把它改写成自底向上的递推。填表顺序从小到大完全避免递归调用也就没有栈溢出的风险。#include iostream #include vector using namespace std; long long stirlingDP(int n, int k) { if (k n) return 0; vectorvectorlong long dp(n 1, vectorlong long(k 1, 0)); dp[0][0] 1; for (int i 1; i n; i) { for (int j 1; j k; j) { dp[i][j] j * dp[i - 1][j] dp[i - 1][j - 1]; } } return dp[n][k]; } int main() { cout stirlingDP(20, 10) endl; return 0; }这个版本和记忆化版本的时间复杂度一样是O(n*k)但空间上还可以进一步优化。观察递推式dp[i][j]只依赖i-1这一行的数据所以完全可以用一维数组滚动更新。不过j的更新方向有讲究由于要用到dp[i-1][j-1]更新j时需要从大到小倒着遍历否则会覆盖待用的旧值。我把这个坑单独拎出来因为面试中很多人改一维数组时都会在这里翻车。3.4 溢出问题当斯特林数大到long long都装不下第三版代码用long long保存结果但对较大的n和k仍然会溢出。第二类斯特林数的增长非常快n30左右很多S(n,k)就已经进入千万亿级别n50时几乎必然超过long long的约9.22e18上限。我处理这个问题的经验是分情况考虑。如果题目只到n30以内long long足够如果n更大有几种可选方案一是用__int128代码改动最小但输出时要自己写转换二是写一个简易的高精度整数类核心就是大数乘法加大数加法不过代码量会上升三是如果允许换成其他语言用Python的大整数最省事。实际做算法题时我通常会先估算S(n,k)的量级再决定用什么类型。有一个粗糙的估算方式S(n,k)的峰值大约在k接近n/2的位置并且量级不会超过k^n/k!也就是n个元素往k个无标号组里塞的组合数上限拿这个做个数量级判断就够用了。4. 进阶实战输出全部划分方案的递归回溯4.1 从“数方案”到“列方案”有的场景不只要计数还要把每种划分方案具体列出来。比如把几台机器上的任务分成k个流水线作业组或者把一组编号按规则拆成k个小队这时候需要的是方案本身而不只是一个数字。计数的递归和列方案的递归思路同源但实现差异很大。计数只需要返回数值并合并列方案则需要维护一个记录当前分组状态的容器在递归过程中推进元素走到递归终点时把容器里的内容打印或保存下来。这种写法也叫递归回溯是分治算法的另一副面孔。4.2 去重是核心如何避免组与组之间的顺序重复直接暴力的思路是对每个元素依次尝试放进k个组中的任意一个。这个思路得到的方案会重复因为同一组划分方式可以被不同的组编号顺序重复输出。比如n3、k2时{1,2}|{3}和{3}|{1,2}在无编号集合意义下是同一种但暴力枚举会把它们当成两种。我的去重技巧是递归时只允许当前元素放入“非空组”或者放入“第一个空组”。一旦放入第一个空组后面的空组在这个分支里就不再考虑。这样保证了同一种划分方式只会按固定的组编号顺序出现一次。#include iostream #include vector using namespace std; int n, k; vectorvectorint groups; long long cnt 0; void dfs(int idx) { if (idx n) { for (int i 0; i k; i) { if (groups[i].empty()) return; } cnt; for (int i 0; i k; i) { cout { ; for (int x : groups[i]) cout x ; cout } ; } cout \n; return; } for (int i 0; i k; i) { if (!groups[i].empty()) { groups[i].push_back(idx); dfs(idx 1); groups[i].pop_back(); } else { groups[i].push_back(idx); dfs(idx 1); groups[i].pop_back(); break; } } } int main() { n 4; k 2; if (k n) { cout 0 endl; return 0; } groups.resize(k); dfs(1); cout total: cnt endl; return 0; }这个去重逻辑的核心在else分支里的break。想象一下如果把第1个元素放进0号组然后递归处理后续元素回溯之后代码不会再尝试把第1个元素放进1号组因为直接break跳出循环。这保证了最小的元素永远停留在编号最小的组里从而砍掉了所有因组排列顺序产生的重复方案。我用n4、k2验证过输出正好是S(4,2)7种不会多也不会少。4.3 剪枝优化与边界保护枚举所有方案的时间复杂度本身就很大因为方案总数是斯特林数增长极快所以实际使用时一定要加剪枝。常见的剪枝有两类。第一类是可行性剪枝递归过程中如果发现剩余元素数量加上当前已有元素都不足以填满剩下的空组就直接返回。比如还剩3个元素没放但还有4个空组这条路肯定走不通不用继续尝试。第二类是顺序剪枝就是上面说的break技巧本质上也属于剪枝——把组排列顺序导致的重复分支直接砍掉。实际写代码时我习惯在main函数里先做kn的判断避免进入DFS做大量无意义的空组检查在dfs的入口也可以提前判断当前空组数量是否大于剩余元素数代码长一点但大数据量下能省非常多时间。5. 复杂度对照与边界条件排查5.1 三种实现复杂度对照表我把集合划分问题的几种实现整理成一个表格方便对照选用实现方案时间复杂度空间复杂度适用场景纯递归O(2^n)O(n)栈深度只适合n在10以内的教学演示分治记忆化O(n*k)O(n*k)经典的算法课和面试标准答案自底向上递推O(n*k)O(n*k)可优化为O(k)工程实现首选递归回溯列方案与方案总数成正比O(n)回溯栈需要具体方案n较小我实际使用时有个优先级如果只需要计数直接上递推如果想展示分治思想用记忆化如果要把方案打印出来才用回溯。不要一上来就写回溯列方案因为它的输出量本身就可能大到离谱。5.2 常见边界条件速查集合划分的边界条件很容易出错尤其是n0、k0这种特殊组合。我踩过几次坑之后整理出了一份速查表输入期望输出常见错误n0, k01有人写成0n0, k00必须保证值为0n0, k00同样返回0kn0很多人忘了这个判断导致递归越界k11递推也能算出来但直接返回更快kn1每元素一组的唯一方案n1, k11同时满足k1和kn注意别抢先返回0处理顺序也很重要。我习惯把边界判断全部放在递归函数的最前面并且把kn的判断放在记忆化查询之前否则memo数组可能访问到不存在的状态。一个小建议把边界条件单独抽出来写不要混在递归逻辑里复查的时候一眼就能看全。5.3 本地实测感受与参数选择建议我自己在本地做了个小测试对比纯递归和记忆化版本的耗时。n20、k10时纯递归版本跑了几十秒都没有结束记忆化版本则是毫秒级返回。n30、k15时记忆化版本依然快但注意结果可能已经逼近long long的极限。把n加到100、k50时连记忆化的二维表都已经有上万个状态虽然时间上还是能接受但结果早就不在标准整型范围内了。所以我的建议很明确做题前先确认n和k的范围。如果n不超过25long long加递推足够如果n在30到50之间考虑__int128或者高精度如果n更大这个题目本身考察的往往是数学性质或者大数运算纯粹的C递推已经不太合适可能需要用斯特林数的其他等价形式来优化。6. 常见问题与排查实录6.1 递归栈溢出纯递归版本在n比较大时递归深度会达到n层。系统栈默认只有几MB空间n到达几千就会栈溢出程序直接崩溃。我当时把n调到5000试过一次马上RecursionError或者Segmentation Fault。解决办法是改用自底向上递推彻底去掉递归调用如果一定要用递归可以尝试改用显式栈模拟但代码复杂度会上升一般不值得。6.2 记忆化数组索引与边界顺序记忆化版本里最容易出的问题不是逻辑错而是memo数组的大小和访问顺序。看我的代码memo初始化为(n1) * (k1)然后dfs的参数n和k在递归中只有n会递减k保持不变所以访问memo[n][k]时行索引n最小会到0列索引k保持初始值不会越界。但如果忘了最外层的kn判断传入的初始k大于n虽然列索引不越界但逻辑上这个状态根本没意义会导致结果错误。我的排查经验是在dfs函数第一行把kn的情况也拦掉配合memo的边界判断双保险。6.3 结果溢出还是超时先判断量级有时程序跑得很快但结果看起来是负数或者错误的大数那就是溢出了。判断方法很简单把输出改成__int128或者double看一眼量级如果明显超过9.22e18就别抱侥幸心理。反过来说如果程序很慢但结果是正确的那就是重复计算太多优先加记忆化而不是优化常数。很多人一听到超时就开始抠循环细节其实在纯递归版本里根本原因是算法复杂度不对不是常数问题。6.4 不要把组合数和斯特林数搞混我在面试别人的时候经常发现有人把S(n,k)和组合数C(n,k)弄混。组合数C(n,k)是从n个元素里选出k个元素答案是子集本身的数量斯特林数S(n,k)是把全部n个元素划分成k个非空组答案是划分方式的数量。两者在n3、k2时数值碰巧都是3容易混淆但n4、k2时C(4,2)6S(4,2)7数值就分开了。做题时先看问题是“选一组”还是“全部分组”这决定了用哪个公式。最后说一点我自己的体会。集合划分这个题目表面上看只是一个递推公式但把它走一遍“分治拆解、递归实现、记忆化优化、递推简化、回溯列方案”的完整链路几乎把算法面试的高频考点都串起来了。我后来遇到类似的问题比如把一组数划分成两个和相等的子集或者把任务按约束分成若干组第一反应都是先问自己这个状态能不能拆成更小的子状态子状态会不会重叠需不需要记忆化带着这套思路去分析很多难题会突然变得清晰很多。如果你正在学分治我建议不要只看理论拿集合划分这种小题目亲手写一遍从慢到快改三轮收获比刷十道新题都大。