1. 子集枚举到底在解决什么问题1.1 一个典型的暴力枚举场景先想一个场景有 n 个物品每个物品都可以“选”或者“不选”问某种条件下有没有解、有多少解、最优值是几。这种题的本质就是把所有选法全部过一遍而“所有选法”的数学名称就是子集枚举。这类题目的数据范围通常很有特点。n 不超过 20 的时候2 的 n 次方大约是 100 万级别普通循环完全可以承受n 不超过 25 时2 的 n 次方是 3300 万勉强能跑一旦 n 到了 302 的 30 次方已经超过 10 亿再用朴素枚举就基本没救了。所以很多老手看到“n 20”这个条件脑子里跳出来的第一个念头就是“枚举所有子集”。这不是什么玄学而是对计算量边界的一种本能反应。子集枚举听着基础但它在后面很多算法里都是“地基”。状态压缩 DP、折半搜索、容斥原理、集合划分哪一样拎出来都得先会“把集合的所有子集列出来”。如果这一步不扎实后面看别人题解里的循环和位运算就会像看天书一样难受。1.2 子集枚举与 DFS、回溯的关系以及什么时候需要它很多初学者一开始接触的是 DFS深度优先搜索然后老师告诉你“DFS 可以用来枚举子集”于是很多人就把“子集枚举”和“深搜回溯”画了等号。其实这是两件事。DFS 是一种搜索框架它强调“沿着一条路走到底再退回来走另一条”子集枚举是一个具体问题它的核心是“把所有组合都看到”。你可以用 DFS 去枚举子集也可以用普通的 for 循环去枚举子集后者甚至更常见。之所以会混在一起是因为有些子集枚举的变形题需要剪枝而剪枝放在 DFS 里更自然。那什么时候需要子集枚举把握几个判断条件第一n 很小通常不超过 20第二你需要对“每个元素选或不选”的所有组合做判断第三题目里出现“集合划分”“分组”“选择一部分物品”“满足某些条件的组合是否存在”这类描述。反过来如果 n 很大或者题目要求输出的是顺序相关的排列而不是组合那就要考虑别的算法了。2. 二进制状态C 里最顺手的子集表示法2.1 一个 int 就是一张“名单”我在给新手讲子集枚举时特别喜欢用一句话开场一个 int 本身就可以是一张集合名单。什么意思二进制数的每一位都可以表示一个元素是否在集合里第 i 位是 1表示元素 i 在子集里第 i 位是 0表示元素 i 不在子集里。举个例子集合元素是 0、1、2、3、4二进制数 00110也就是十进制的 6表示的是 {1, 2}因为第 1 位和第 2 位是 1。空集就是 0全集就是 (1 n) - 1也就是从第 0 位到第 n-1 位全是 1。为什么要强调下标从 0 开始因为这样位运算写起来最顺手。1 i天然代表元素 imask里的第 i 位要不要某个元素直接用位运算操作完全不需要额外转换。如果非要把集合元素编号成 1 到 n那每次都得写成1 (i - 1)丑不说还特别容易出错。所以刷题的时候凡是准备用二进制表示集合的第一步就是把元素重新编号成 0 到 n-1。2.2 子集运算对照表用二进制表示集合之后常用的集合操作都能用位运算搞定。这一张表我建议你直接抄下来贴在电脑旁边操作写法说明判断第 i 位是否存在(mask i) 1结果为 1 表示存在添加第 i 位mask | (1 i)把第 i 位变成 1删除第 i 位mask ~(1 i)把第 i 位变成 0翻转第 i 位mask ^ (1 i)原来是 0 变 1是 1 变 0交集a b两边都有的元素并集a | b至少一边有的元素补集相对全集full ^ maskfull 是全集判断 sub 是否是 mask 的子集(mask sub) sub注意括号不能省取最低位的 1mask -mask也叫 lowbit后面经常用这个 lowbit 操作特别重要它在子集枚举、树状数组、状压 DP 里都是高频操作。原理也不复杂负数在计算机里用补码表示取负号相当于按位取反再加 1所以x -x正好能把最低位那个 1 单独抠出来。2.3 为什么下标从 0 开始做题更舒服我见过不少新手习惯把输入的编号直接当成二进制位来用结果代码写得又长又绕。比如一个集合的元素是 1、2、3有人一上来就写1 x然后发现元素 1 占的是第 1 位很快就乱了。在算法竞赛里元素编号从 0 开始是约定俗成的尤其是用位运算的时候。空集用 0 表示全集用(1 n) - 1表示低位的编号、高位的编号一目了然。如果题目输入是 1 到 n建议读入后立刻改成内部编号 0 到 n-1处理完再根据题目要求输出。这只是个习惯问题但习惯好的人写出来的代码干净、不容易出 bug调起来也快得多。3. 两套主流实现循环枚举与递归枚举3.1 循环写法全集遍历模板先看最直接的写法。n 个元素的集合所有子集一共 2 的 n 次方个从 0 到 (1 n) - 1 每个数字都对应一个子集所以直接一个 for 循环就能遍历完。#include bits/stdc.h using namespace std; int main() { int n 4; for (int mask 0; mask (1 n); mask) { cout mask : ; for (int i 0; i n; i) { if ((mask i) 1) { cout i ; } } cout \n; } return 0; }输出结果是 0: 空集1: 02: 13: 0 14: 25: 0 2……顺序有点跳跃但这恰恰是二进制递增带来的自然顺序每一个 mask 都唯一对应一个子集。这个模板胜在简单、直观、好记。只要题目要求“把所有子集都看一遍”而且不需要中途剪枝直接用它准没错。需要用到子集编号做下标的时候也方便比如下面用数组sum[mask]存每个子集的和mask 本身就是数组下标。3.2 递归写法选或不选的模型第二种写法是递归模型非常经典我叫它“选或不选”模型。void dfs(int idx, int mask, int n) { if (idx n) { // 已经处理完所有元素mask 就是当前子集 return; } // 不选元素 idx dfs(idx 1, mask, n); // 选元素 idx dfs(idx 1, mask | (1 idx), n); }从第 0 号元素开始每个元素分两个分支不选它状态不变选它把第 idx 位改成 1。递归走到 idx n 的时候mask 就代表一个合法子集。这种写法的好处是可以在递归过程中多维护一些信息比如当前子集的和、当前选了几个元素、当前是否已经满足某个条件。很多剪枝优化需要在搜索过程中“边走边判断”这时候递归写法的优势就体现出来了。缺点是代码量稍大一点而且如果状态不是用普通 int 传值而是用全局数组记录就得小心回溯时恢复状态。3.3 怎么选性能、代码量与可读性的权衡循环枚举和递归枚举最终产生的子集集合是完全一样的时间复杂度也都是 O(2 的 n 次方)。区别在于使用场景。写法优点缺点适合场景循环枚举代码短容易想mask 可直接做下标不太好边枚举边剪枝暴力找答案、预处理子集信息递归枚举方便剪枝和携带额外信息代码稍长容易递归深度出错需要搜索优化、需要当前状态参数我自己的习惯是如果只是“把所有子集扫一遍”用循环如果题目里带“找是否存在某种组合”“求最优解”这类需要提前终止的条件优先考虑递归。实际上很多题两种都能过但提前想清楚哪种更适合能少走不少弯路。比如“子集和”问题递归写法可以做到当前和超过目标直接 return循环写法就只能把所有子集全部算完再判断。4. 三个必须掌握的进阶姿势固定大小、子集套子集、剪枝4.1 只枚举大小为 k 的子集有时题目会限制“只能选 k 个元素”这时候全量枚举所有子集再判断个数是一种办法但效率太低。更优雅的做法是直接“生成所有大小为 k 的子集”。最简单的写法是递归选 k 个不重复的元素void dfs(int start, int cnt, int mask, int n, int k) { if (cnt k) { // 得到一个大小为 k 的子集 return; } if (start n) return; for (int i start; i n; i) { dfs(i 1, cnt 1, mask | (1 i), n, k); } }这个方法每次从 start 之后开始选保证不会重复也不会出现排列顺序的问题。还有一个进阶技巧叫 Gosper’s Hack专门用来按二进制大小顺序生成“恰好含有 k 个 1”的数字。代码是这样int state (1 k) - 1; int limit 1 n; while (state limit) { // 处理当前 state int c state -state; int r state c; state (((r ^ state) 2) / c) | r; }很多人第一次看到这个公式会有点懵。它的本质是模拟二进制进位把最低位的一串连续的 1 进位到更高位然后把低位重新铺成最小的连续 1。初学阶段不理解也不影响使用先背下来等位运算熟练之后自然能看懂。对于竞赛新手我建议优先掌握递归写法Gosper’s Hack 可以作为扩展储备。4.2 枚举“子集的子集”与 3 的 n 次方复杂度有一种更高频的枚举方式出现在许多状态压缩 DP 和容斥题目里给定一个集合 mask要枚举它的所有子集。写法非常固定for (int sub mask; sub; sub (sub - 1) mask) { // 这里 sub 是 mask 的非空子集 } // 空集可以单独处理这段代码的精髓在(sub - 1) mask。每次把 sub 减 1再和 mask 做按位与会跳过那些本来就不在 mask 里的位直接跳到下一个子集。你可以想象成“在一个被 mask 限制的二进制范围内倒序枚举”不会漏也不会重复。如果你要枚举“所有集合的所有子集”代码就是嵌套两层for (int mask 0; mask (1 n); mask) { for (int sub mask; sub; sub (sub - 1) mask) { // 处理 sub } }这里有一个非常重要的复杂度结论总复杂度不是 O(2 的 n 次方乘以 2 的 n 次方)而是 O(3 的 n 次方)。原因是每个元素有且只有三种状态不在 mask 里、在 mask 里但不在 sub 里、同时在 mask 和 sub 里。所以总数是所有组合数乘以对应子集数求和正好等于 3 的 n 次方。也就是说n 15 时大约是 1400 万n 20 时就到了 34 亿直接超时。所以这种写法一般限制在 n 15 左右的题目里。4.3 剪枝别把不存在的组合跑到底子集枚举最大的问题就是指数级爆炸所以剪枝往往是能不能过的关键。举一个最经典的例子给定 n 个正整数问是否存在一个子集使得子集和为 target。递归枚举时如果当前已经选了的数字的和已经大于 target那后面不管怎么选都不可能等于 target 了因为都是正数。这时候可以直接 return不再继续递归下去。void dfs(int idx, int sum, int target, int n) { if (sum target) { found true; return; } if (idx n || sum target) return; // 不选 dfs(idx 1, sum, target, n); // 选 dfs(idx 1, sum w[idx], target, n); }别小看这一句sum target在随机数据下它能砍掉大量分支。最坏情况复杂度当然还是 O(2 的 n 次方)但实际运行速度可能快好几个数量级。这就是剪枝的意义。5. 实战拆解一道题看清子集枚举的完整套路5.1 完整代码与运行过程看一道很常见的入门题给定一个数组问能不能把它分成两组使得两组元素之和相等。举一个生活化点的说法就是“把这堆数分成两份让两边一样重”。思路其实不复杂如果总和是奇数肯定不可能直接输出 NO。如果是偶数目标值就是总和的一半记为 half。接下来枚举所有子集如果某个子集的和等于 half说明剩下的元素之和也等于 half答案就是 YES。朴素的做法是每枚举一个 mask 就循环累加一次子集和复杂度是 O(n 乘以 2 的 n 次方)。我们可以预计算一个 sum 数组用 lowbit 递推每个 mask 的和把复杂度降到 O(2 的 n 次方)。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint w(n); int total 0; for (int i 0; i n; i) { cin w[i]; total w[i]; } if (total % 2) { cout NO\n; return 0; } int half total / 2; vectorint sum(1 n, 0); // 用 lowbit 递推每个子集的和 for (int mask 1; mask (1 n); mask) { int lb mask -mask; int idx __builtin_ctz(mask); // 最低位 1 的索引 int prev mask ^ lb; // 去掉最低位后剩下的子集 sum[mask] sum[prev] w[idx]; } bool ok false; for (int mask 0; mask (1 n); mask) { if (sum[mask] half) { ok true; break; } } cout (ok ? YES : NO) \n; return 0; }注意__builtin_ctz要求参数不能是 0所以 sum 的递推从 mask 1 开始mask 0 的子集和本来就是 0不用算。这段代码的关键理解点在于去掉最低位的 1 之后剩下的 mask 一定比当前 mask 小所以它的 sum 早就计算好了直接拿来加一个元素的值就行。这就是“用已经算出来的状态算新状态”的雏形也是状态压缩 DP 的核心思路。5.2 从暴力枚举到状态压缩 DP 的一步之遥很多人觉得状态压缩 DP 很难其实它和刚才这道题的思路是连续的。刚才我们预计算了 sum[mask] 数组本质上就是一种“以 mask 为状态”的递推。状态压缩 DP 无非是把这个思想再往前推一步在枚举所有 mask 的过程中给每个 mask 额外记录一个或者若干个信息然后通过前面的 mask 递推出来。举一个常见的过渡例子旅行商问题的简化版有 n 个城市从一个城市出发每个城市只能去一次问最短路径。如果 n 15就可以用 dp[mask][i] 表示“我已经去过的城市集合是 mask当前停在第 i 个城市”的最短距离。转移的时候枚举下一个还没去过的城市 j更新 dp[mask | (1 j)][j]。正是因为在第 4 步、第 5 步这类题目里反复用过“枚举子集、用 mask 表示状态、通过 lowbit 或子集关系递推”这些操作后面看状态压缩 DP 才会觉得水到渠成。所以千万不要觉得初级第 3 篇只是在讲“怎么列出子集”它其实是在给你构建一套底层直觉。6. 常见问题与排查技巧实录6.1 位运算优先级你写的条件可能根本没生效我见过的子集枚举 bug 里有一半以上都和运算符优先级有关。最常见的一个坑是这样写if (mask (1 i) 0) { // 想判断第 i 位不存在 }这段代码实际执行顺序是先算(1 i) 0这个肯定是 false也就是 0然后算mask 0整段表达式永远是 0条件永远成立。于是你的 if 分支永远都会进看起来完全不受控制。正确写法是加括号或者换个姿势判断if ((mask (1 i)) 0) // 加括号 if (!((mask i) 1)) // 先移位再与1我自己的习惯是尽量写(mask i) 1这样不仅避开了优先级问题读起来也更直观把第 i 位移到最低位然后看是不是 1。另外判断子集关系时(mask sub) sub这组括号也不能丢否则真相会再次让你怀疑人生。6.2 移位越界n 31 之后怎么办1 n看着简单但在 n 比较大的时候会翻车。int 通常只有 32 位1 31已经是最左边的符号位结果是个负数再往左移就是未定义行为可能直接得到完全没规律的数字。所以所有涉及1 n的地方都要先想清楚 n 的范围。如果 n 可能接近或者超过 30建议写成1LL n提升到 long long。但更重要的是真正枚举到 2 的 30 次方以上的场景已经很少见因为时间上根本跑不完。真遇到 n 30 甚至 n 40 的题目老手考虑的是折半搜索而不是头铁枚举全集。6.3 递归枚举不恢复状态下次循环全乱套递归枚举如果用的是值传递的 mask回溯时其实不需要恢复什么因为每个分支拿到的都是副本。但很多新手喜欢用全局数组来记录“当前选了哪些元素”比如vectorbool chosen(n, false); void dfs(int idx) { if (idx n) { process(); return; } chosen[idx] true; // 选 dfs(idx 1); chosen[idx] false; // 不选 dfs(idx 1); }注意这个写法里chosen[idx] false必须在第二个 dfs 之前执行否则从“选”的分支回来时数组状态还是错的。更常见的写法是“先不选再选”或者“选完立刻还原”chosen[idx] false; dfs(idx 1); chosen[idx] true; dfs(idx 1); chosen[idx] false; // 恢复无论是哪种写法核心原则只有一个递归入口进去之前的状态和出口之后的状态必须完全一样。这个原则在走迷宫、全排列、八皇后里同样适用属于回溯算法的基本功。6.4 复杂度从 O(2^n) 到 O(n*2^n) 的隐藏坑最后聊一个让不少人超时的暗坑。很多人知道枚举全部子集是 O(2 的 n 次方)但忽略了内层还要循环 n 次去检查每个元素是否在子集里。于是实际复杂度变成了 O(n 乘以 2 的 n 次方)。当 n 20 时2 的 20 次方约 100 万乘以 20 变成 2000 万还好当 n 25 时2 的 25 次方约 3300 万乘以 25 就是 8 亿多这就非常危险了。所以如果题目要求你对每个子集都做一次“遍历所有元素”的操作优先考虑能不能预计算。比如前面分组题里的 sum[mask]就是通过 lowbit 把 O(n*2^n) 变成了 O(2^n)。还有专门统计子集中元素个数的__builtin_popcount(mask)也是编译器优化好的比手动循环快很多。养成“能预计算就预计算”的意识到了状态压缩 DP 阶段会非常省心。子集枚举的坑说到底集中在位运算优先级、移位边界和状态恢复这三类。我自己当年也是被 “mask (1 i) 0” 这个表达式坑了好几次才长记性的。建议你把前 4 节的模板抄下来一个一个跑一遍把 0 到 (1 4) - 1 每个 mask 对应的子集都亲手列一遍这对后面写状压 DP 的帮助会非常大。