如果只看标题，你可能会觉得"C++分治算法之集合划分问题"是个很小众的题型，顶多出现在某些算法课程期末或者竞赛题库里。但实际上，我过去在好几个项目里都被它卡过：一次是给某个模拟系统做资源分配，要把一批任务分给多个执行节点，求划分方案数；另一次是在分析一组实验数据时需要把样本分成两组，让两组的总量尽可能接近。前者是"计数型集合划分"，后者是"最优平衡型集合划分"，两个问题长得像，解法思路完全不同，而分治算法在这两类问题里都有非常关键的应用场景。
这篇内容主要解决三件事：第一，集合划分问题为什么不能靠枚举硬扛；第二，用分治思想去做划分计数的核心递归关系；第三，真正把集合"对半劈开"各自枚举再合并的 Meet-in-the-Middle 做法，以及落地 C++ 时的各种注意点。适合正在学算法、准备面试，或者工作中偶尔要处理组合优化问题的同学参考。我会直接贴代码、讲复杂度，再把我踩过的坑一并写出来。
1. 集合划分问题的两种形态，以及为什么必须动用分治
1.1 先分清你要解的是哪一类集合划分
集合划分问题在我这儿的定义很简单：把一个给定的集合 (S={a_1,a_2,\dots,a_n})，按某种规则拆成若干子集。规则不同，解法天差地别：
- 无约束计数型：把 (n) 个互不相同的元素划分成 (k) 个非空子集，问一共有多少种划分方法。这个数叫第二类斯特林数 (S(n,k))，而所有可能划分的总数是贝尔数。
- 约束优化型：把集合划分成若干个子集，使得子集和满足某个条件，比如两个子集的和相等，或者两组和的差最小。经典的就是"数组分成两组，两组和尽量接近"。
很多人一开始都会想用递归枚举：每个元素放进哪个组？状态直接爆炸。只要 (n) 到二十几，纯枚举就不可能跑完。因为一个 (n) 元素集合的全部子集数量是 (2^n)，而所有划分数目更是远超 (2^n)。这时候分治算法的作用就体现出来了：把一个规模为 (n) 的复杂问题，拆成若干个规模减半的子问题，分别求解后合并答案。
1.2 分治不是"一招鲜"，关键是找到可合并的分解方式
分治算法在集合划分问题里有两种完全不同的切入点，我会在后面分别展开：
- 情况分解：某一类计数问题可以按"某个特定元素最后去哪了"来拆成两个互斥情况，每个情况又对应一个规模更小的同类问题。这是自顶向下的递归分治思想。
- 集合对半分解：把集合按元素下标分成左右两半，分别枚举这两半内部的所有子集情况，再用排序、二分或双指针把左右的结果合并起来，解决最优化问题。这就是 Meet-in-the-Middle，常被翻译成"折半搜索"或"中途相遇"。
很多教程把分治算法单纯等同于快速排序、归并排序这类"拆成两半再合并"的套路，导致遇到集合划分问题时想不起来用。实际上，分治的核心不在于"切成两半"这个动作，而在于拆出来的子问题必须能被快速合并。计数型集合划分中，合并规则是加法原理；优化型集合划分中，合并规则是用有序数组和双指针找最优匹配。理解了这一点，你才算真正会用分治。
2. 从计数问题先下手：最后一个元素"去哪了"的分治递归
2.1 第二类斯特林数的经典递归式
先做一个热身：计数型集合划分，也就是求第二类斯特林数 (S(n,k))。定义是把 (n) 个不同元素分到 (k) 个非空、无标号（也就是不考虑盒子顺序）的子集中。
很多人看到这个定义会直接去写全排列枚举，然后发现 (n) 只要到 10 就已经有一千多万种划法。标准解法是用递归关系：
[ S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k) ]
这个式子我在面试和实际项目里都不止一次被问过，很多人只背公式却不理解它的分治含义。其实它的推导就是分情况讨论一个特殊元素——通常是最后一个元素：
- 情况 A：这个元素自己单独成为一个子集。那么其余 (n-1) 个元素必须分成 (k-1) 个非空子集，方案数是 (S(n-1,k-1))。
- 情况 B：这个元素加入已有的某个子集。那么其余 (n-1) 个元素要分成 (k) 个非空子集，然后再决定这个新元素放进哪一个子集。因为有 (k) 个可选的子集，所以方案数是 (k \cdot S(n-1,k))。
两种情况的边界条件分别是：(k=0) 或 (n<k) 时无方案，返回 0；(k=1) 或 (k=n) 时只有 1 种方案。这就是一种典型的分而治之：把一个规模 ((n,k)) 的问题，拆成两个规模更小的子问题，其中一个参数减小，另一个还用同样的 (k)。子问题之间互不重叠，答案直接相加。
2.2 递归记忆化的 C++ 实现
理解了上面两个 Case 之后，代码写起来非常直接。为了更快我通常给递归加上记忆化数组，避免重复计算同一个 ((n,k))：
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007LL; const int MAXN = 505; ll memo[MAXN][MAXN]; ll stirling(int n, int k) { if (k == 0 || k > n) return 0; if (k == 1 || k == n) return 1; if (memo[n][k] != -1) return memo[n][k]; // 分治：最后一个元素单独一组 + 最后一个元素加入已有某一个组 ll res = (stirling(n - 1, k - 1) + (ll)k * stirling(n - 1, k) % MOD) % MOD; return memo[n][k] = res; } int main() { int n, k; cin >> n >> k; memset(memo, -1, sizeof(memo)); cout << stirling(n, k) << '\n'; return 0; }这里我用-1初始化memo，因为合法的方案数可以是 0，用0来做"未计算"标记会很麻烦。复杂度上，虽然递归入口只有一个，但因为记忆化，每个 ((n,k)) 最多算一次，状态数是 (n \cdot k) 级别，时间复杂度为 (O(nk))。
2.3 为什么大参数时要转成自底向上的 DP
如果你在某个判题系统上提交上面的递归代码，当 (n,k) 小于 500 时基本没问题，但一旦超过几千，递归深度和函数调用开销就会成为瓶颈。这时候要把递归形式改造成二维动态规划，也就是自底向上的填表。
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007LL; int main() { int n, k; cin >> n >> k; vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 0)); dp[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= min(i, k); ++j) { dp[i][j] = (dp[i - 1][j - 1] + (ll)j * dp[i - 1][j]) % MOD; } } cout << dp[n][k] << '\n'; return 0; }注意我让dp[0][0] = 1，这样递推初始状态更干净，事实上 (S(0,0)=1)，而任何 (S(n,0)) 都会是 0。
从这个转移可以看出，分治递归和 DP 本质上是在用不同顺序遍历同一张状态表。如果只是为了求单个 (S(n,k))，递归记忆化代码更好读；如果后续还要拿整张表做其他递推，比如求贝尔数 (B(n)=\sum_{k=0}^n S(n,k))，那就用 DP。
2.4 这种"递归拆情况"的适用边界
第二类斯特林数用分治转 DP 非常顺，但它只适合 (n) 在 (10^3) 到 (10^4) 范围内的计数场景。如果 (n) 到达 (10^5) 甚至 (10^6)，(O(nk)) 也会超时，就需要生成函数、NTT 之类的更高级技巧了，不过那已经超出一般项目需求，我在实际工作中很少遇到。
另外要提醒一点：这套递归关系只适用于"元素互不相同"的集合。如果集合里有重复元素，或者划分出来的子集被要求带标号（比如分成不同的队伍、不同的箱子），递推式都要重新调整。我见过有人把无标号集合划分的题硬套这公式，结果差了好几倍，原因就是忽略了标号带来的组合因子。
3. 真正对半分：平衡划分问题与 Meet-in-the-Middle
3.1 需求场景：把集合分成两组，让两组和尽量接近
计数型集合划分虽然原理清晰，但实践里我更常遇到的是优化型。比如给定一个长度为 (n) 的整数数组，要求把所有元素分成两组，使得两组元素之和的差最小。等价于在数组里选出一个子集，让子集和尽量接近总和的一半。这类问题也叫"数组分割问题"。
当 (n \le 20) 时，我会直接用暴力枚举子集，因为总共只有 (2^{20} \approx 100) 万种情况。但当 (n) 到 30、40，甚至 60 的时候，纯枚举就完全不可行了。分治算法的切入点非常自然：把数组下标劈成左右两半，每半长度约 (n/2)，各自枚举所有子集，再想办法把左右两半的子集合并起来，找出最优组合。
3.2 为什么复杂度从 (2^n) 降到大约 (2^{n/2})
先看纯暴力：枚举大小为 (n) 的集合所有子集，得到每个子集的和，然后找最接近total/2的那个和，复杂度 (O(2^n))。当 (n=40) 时，(2^{40}) 约等于 10 的 12 次方，这个数量级在现代计算机上跑起来都是几分钟起步，在判题系统上直接超时。
但如果把集合分成左右两半，左边长度 (n_1)，右边长度 (n_2)，单独枚举左右子集和的成本只有 (O(2^{n_1} + 2^{n_2}))。两边各自生成约 (2^{n/2}) 个候选和，再把右半候选排序，对左半每个候选和目标值做二分查找，整体复杂度约为：
[ O(2^{n/2} \cdot \log 2^{n/2}) ]
当 (n=40) 时，这个量级只有大约 2 的 20 次方，也就是百万级别，和原来的万亿级别差了六个数量级。这就是"中途相遇"的威力，我用一个生活化类比：你想找两个人加起来正好 180cm，不需要让所有人两两互相量身高，而是先把一半人报数排队，另一半人逐个进去用二分查身高。
3.3 完整 C++ 实现：枚举、排序、二分合并
我给一个可以直接抄的实现。数组长度 (n) 可以到 45 左右，当然具体能跑多大取决于判题机性能和时限。
#include <bits/stdc++.h> using namespace std; using ll = long long; // 返回 vector 中某个子集从下标 0 到 m-1 的所有可能和 vector<ll> enumSubsetSums(const vector<ll>& v) { int m = (int)v.size(); vector<ll> res; int totalMasks = 1 << m; res.reserve(totalMasks); for (int mask = 0; mask < totalMasks; ++mask) { ll sum = 0; for (int i = 0; i < m; ++i) { if (mask & (1 << i)) sum += v[i]; } res.push_back(sum); } return res; } int main() { int n; cin >> n; vector<ll> a(n); ll total = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; total += a[i]; } if (n == 1) { cout << a[0] << '\n'; return 0; } int mid = n / 2; vector<ll> leftPart(a.begin(), a.begin() + mid); vector<ll> rightPart(a.begin() + mid, a.end()); vector<ll> sumL = enumSubsetSums(leftPart); vector<ll> sumR = enumSubsetSums(rightPart); sort(sumR.begin(), sumR.end()); // 目标是找一组和为 closeTarget，使得 |total - 2 * sum| 最小 ll closeTarget = total / 2; ll bestDiff = LLONG_MAX; for (ll s : sumL) { // 在右半枚举和里找最接近 (closeTarget - s) 的值 auto it = lower_bound(sumR.begin(), sumR.end(), closeTarget - s); if (it != sumR.end()) { ll sum = s + *it; bestDiff = min(bestDiff, llabs(total - 2 * sum)); } if (it != sumR.begin()) { --it; ll sum = s + *it; bestDiff = min(bestDiff, llabs(total - 2 * sum)); } if (bestDiff == 0) break; } cout << bestDiff << '\n'; return 0; }这段代码里有几个细节值得说明：
enumSubsetSums里用mask的二进制位代表"某个元素选还是不选"，这是集合子集枚举最直接的方式。因为左右两部分最多各自二十几个元素，用一个int的 mask 就够。如果单边长超过 31，就必须改用unsigned long long来当 mask。- 排序放在
sumR上，二分查找用lower_bound找closeTarget - s，这个值可能不在数组中，所以要同时检查命中的位置和前一个位置，取两者中更接近目标的值。 bestDiff == 0就直接 break。因为差为 0 已经达到理论最優，没必要继续枚举。
3.4 拿一组小数据手算验证
我用一个被我在笔记里写了无数遍的例子：[3, 1, 4, 2, 5]，总和 (15)，目标是让两组和尽可能接近 (7.5)。
把数组分成左半[3,1]、右半[4,2,5]。左半子集和是：
- 0、3、1、4
右半子集和是：
- 0、4、2、5、6、9、7、11
排序后右半是[0,2,4,5,6,7,9,11]。左半的4对应要去右半找3.5，lower_bound会找到4，和为8，差值 (\lvert 15-16\rvert=1)。这就是最优解：左半边全选{3,1}，右半边选{4}，两组和分别是 8 和 7，差为 1。
这组数据很小，但你注意观察"左半归左半、右半归右半"的一个重要前提：我们在合并阶段允许任意组合左右两半的子集，也就是说最终分到同一边的元素可能来自左半也可能来自右半。Meet-in-the-Middle 之所以正确，是因为每个元素只有"进入第一组"和"进入第二组"两种选择，而左右两半的选择是独立的，最后通过求和就能还原出整个划分。
4. 合并阶段的核心细节：排序、双指针与进一步压缩
4.1 排序加二分的意义与复杂度
有初学者会问：既然最终目标和是确定的，为什么不直接枚举右半所有和，对每个左半和也枚举右半所有和？因为这样合并成本就是 (2^{n/2} \times 2^{n/2} = 2^n)，分治就白分了。排序的意义在于把右半候选变成有序数组，然后用二分查找把右半的扫描成本从 (O(2^{n/2})) 降到 (O(\log 2^{n/2}))。
不过在实际项目中，我会稍微换一个角度：排序除了支持二分，还能顺手去重。如果数组里有大量重复值，候选和会重复出现，去重之后能省下不少内存和二分时间。不过要注意，去重后如果还需要输出具体划分方案，就不能简单去重了，得额外记录每个和对应的 mask，这个我项目里做得比较多。
4.2 用双指针把合并再降一档
如果目标不是找到精确等于某个值的子集和，而是要让两边尽量平衡，那么也可以不用二分。把左半和右半都排序后，一个经典的技巧是双指针：一个指针从左往右遍历左半和，另一个指针从右往左遍历右半和。
sort(sumL.begin(), sumL.end()); sort(sumR.begin(), sumR.end()); int i = 0, j = (int)sumR.size() - 1; ll bestDiff = LLONG_MAX; while (i < (int)sumL.size() && j >= 0) { ll cur = sumL[i] + sumR[j]; bestDiff = min(bestDiff, llabs(total - 2 * cur)); if (cur < closeTarget) { ++i; // 和还不够大，从左边取更大一点的和 } else { --j; // 和太大了，从右边取更小一点的和 } }这个做法的复杂度是 (O(2^{n/2}))，比二分法的 (O(2^{n/2} \log 2^{n/2})) 又低了一截。要注意的是，双指针默认左右两个数组都是有序的，并且题目没有"必须非空"之类的限制。如果要求两组都必须至少有一个元素，那合并在枚举时就要排除 mask=0 或 mask=全集的情况，这一点会在后面避坑部分详细说。
4.3 当 n 在 30 以内时：用 bitset 做等和划分
如果题目只问"能不能分成两个和相等的子集"，且 (n \le 30)、总和不是很大，那么还有一个更快的压位手段：std::bitset背包。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); int total = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; total += a[i]; } if (total & 1) { cout << "NO\n"; return 0; } bitset<200005> dp; dp[0] = 1; for (int x : a) { dp |= (dp << x); } cout << (dp[total / 2] ? "YES" : "NO") << '\n'; return 0; }这个代码的本质是把"子集和是否可达"压成一个布尔数组，每次新增一个元素，所有已有可达状态都左移x位。当total不超过几十万时，bitset 非常快。但它的弱点也很明显：只能判断等和划分，不能很好处理绝对值最小化的差，而且总和过大时会爆内存。所以我通常在项目评估阶段先用 bitset 做可行性检查，再用 Meet-in-the-Middle 求具体最优值。
4.4 负数、零和重复元素怎么办
数组里有负数会直接影响枚举顺序。最简单的方法是把所有元素统一平移，比如全部加上一个足够大的偏移量使每个元素都为正，然后求等和划分时记得把偏移也处理掉。但平移会让总和上限变大，有时反而更慢。另一个思路是继续用 Meet-in-the-Middle，枚举左右半子集和时会自然包含负和，排序照样能处理，只是二分查找的closeTarget需要小心。
重复元素在分治枚举里不算大问题，因为mask按位置区分每一个元素，即便它们的值相同，在划分里也应当被当成独立个体。但如果题目说"相同值的元素视为相同"，那就不能用这种逐元素枚举了，而要用多重集组合计数。
5. 实战踩坑：从状态溢出到错误剪枝
5.1 mask 用int还是unsigned long long
我最早写枚举时习惯用int mask，单边元素数量超过 30 就会出问题：1 << i本身是int，移位到符号位之后就变成未定义行为或错误数值。后来我统一规定：只要 (\frac{n}{2}) 可能超过 29，mask 就用uint64_t，并且移位用1ULL << i。
using ull = unsigned long long; vector<ll> enumSubsetSums(const vector<ll>& v) { int m = (int)v.size(); vector<ll> res; ull totalMasks = 1ULL << m; res.reserve((size_t)totalMasks); for (ull mask = 0; mask < totalMasks; ++mask) { ll sum = 0; for (int i = 0; i < m; ++i) { if (mask & (1ULL << i)) sum += v[i]; } res.push_back(sum); } return res; }别小看这个细节，n=40 时左右各 20，int还能撑住；一旦左右分得不均衡，比如一边 31 个，另一边 9 个，1 << 30都没问题，但1 << 31就是一个负数掩码了，结果直接错。
5.2 vector 而不是 set 来存候选和
有人为了"顺带去重"会把枚举结果放进std::set。我强烈不建议在枚举阶段用 set，因为插入成本是 (O(\log k))，大量插入会有严重的常数开销。正确做法是用vector先收集，全部收集完后统一sort + unique。包含头文件#include <bits/stdc++.h>在竞赛环境里没问题，工程上我更倾向于按需包含具体头文件，但核心思路不变。
5.3 奇数的总和与整数除法
求closeTarget = total / 2时，如果total是奇数，total/2会向下取整。这在二分阶段没有问题，因为我会同时检查lower_bound前后的两个位置，最终差值取的是llabs(total - 2*sum)，能够正确处理小数意义上的 0.5 偏差。但如果你直接写if (sum == closeTarget)之类判断，奇数总和时就永远找不到精确解，必须用差值判断。
5.4 递归深度并不是分治的死穴，但要注意栈
第二类斯特林数的递归记忆化，深度最多是 (n)，当 n=5000 时递归栈已经比较危险。我实际项目里 n 最多到几千，所以会直接用 DP 数组。而 Meet-in-the-Middle 的递归深度只取决于归并排序或枚举函数嵌套，通常很浅，反而不用担心。如果你的分治实现里用到了递归划分数组、递归生成子集和，那每层递归都复制vector会带来很大的拷贝成本。我一般用下标区间加一个全局数组来避免频繁拷贝，并且在递归边界明确调用reserve。
5.5 必须非空子集时的特殊处理
有些题目会要求划分出的两组都非空，那在 Meet-in-the-Middle 合并时就要排除 mask=0（即左半一个都不选且右半也一个都不选，会得到 sum=0）。更麻烦的是，最优值可能选用了左半空子集和右半某个子集，或者左半某个子集和右半空子集，只要排除掉"左右两边全不选"即可，但如果题意要求两组非空，那么任意一边为空都是非法的。建议在枚举时增加过滤条件：
for (ull mask = 0; mask < totalMasks; ++mask) { if (mask == 0) continue; // 至少选一个元素 if (mask == totalMasks - 1) continue; // 至少留一个元素给别人（可选） // ... }这里mask == totalMasks - 1表示当前半边所有元素都被选入同一边，需要结合题意决定是否允许。
6. 我的一点工作心得：分治集合划分的真正价值
前两个月我帮一个项目做任务调度模块，需求是把约 38 个耗时任务分成两组，尽量让两组总耗时接近，好并行执行。当时我第一反应就是动态规划，但发现总耗时的量级非常大，DP 数组根本开不下。后来改成 Meet-in-the-Middle，40 个任务的规模在几百毫秒内就给出了接近最优的解。这让我再次确认：分治不只是竞赛套路，处理真实世界中"穷举太多"的问题非常实用。
如果要在工作中快速判断该不该用分治，我的经验是三条：
- 如果 (n \le 20)，直接枚举全子集。
- 如果 (n) 在 30 到 45 之间，且问题可以拆成左右两半各自枚举、最后合并，优先用 Meet-in-the-Middle。
- 如果总和规模不大，想要快速判断可行性，先用 bitset 背包筛一遍，不行再上 MITM。
这套组合拳我已经在好几个模拟项目里用过了，基本没有翻过车。真正需要留意的反而是对题意的理解：是非空子集还是允许空集？是否需要输出具体划分方案？元素是否要区分顺序？只要这些问题在写代码前想清楚，剩下的难点其实都集中在合并阶段的排序和边界查找上。
最后分享一个小技巧：写完分治代码后，先用 (n \le 20) 的随机数据对拍，一边跑暴力枚举，一边跑 Meet-in-the-Middle，两个结果必须完全一致。对拍能在一小时内找出绝大多数 border case，这比盯着代码干瞪眼高效得多。集合划分问题看起来抽象，一旦你把它拆成"枚举左半、枚举右半、合并答案"三步走，思路就会清晰很多，C++ 实现也会变得顺理成章。
