枚举子集 · 2ⁿ · 四种算法

枚举全部子集：四种算法

幂集一页把一个集合的全部子集按大小铺开；这一页换个问法：给定一个集合，用不同的算法不重不漏地逐一生成它的全部子集。n 个元素的子集共 2ⁿ 个——每个元素独立地「选 / 不选」，两种选法相乘。下面四种算法都能枚举出这 ${2^n}$ 个子集，差别只在枚举的次序与视角——每种算法各有一块 board，点亮的是同一批子集，只是次序与节奏不同。用全部播放可让四种算法从头同步开跑，直观对比它们的推进方式。

1 · 二进制计数 bitmask：把「选 / 不选」向量当成一个数

bitmask · mask ∈ 0 .. 2ⁿ−1

给 n 个元素编号 ${0 .. n-1}$ ，一个子集就是一串「选 / 不选」——恰好是一个 n 位二进制数 mask。让 mask 从 0 数到 ${2^n - 1}$ ，第 i 位为 1 就把 els[i] 收进子集。整数与子集一一对应，数完全部整数即枚举出全部子集。

为什么最省事：它把「枚举子集」直接化归成「从 0 数到 ${2^n - 1}$ 」，只用一个整数循环、无递归、无额外内存。工程里用一个整型的位表示一个集合（位运算做并 / 交 / 差），正是这套思路——代价是 mask 的位序与元素的对应要记牢。

2 · 逐元素递归：每个元素「入选或不入选」

recursion · 每元素 2 种去处

把元素排定顺序逐个表态：第 i 个元素要么不入选、要么入选，两条分支各自往下递归。递归到最后一个元素，每条决策路径恰好对应一个子集—— ${2^n}$ 条叶子路径与 ${2^n}$ 个子集一一对应。这与枚举划分的逐元素递归同形，只是每个元素的去处从「k + 1 个块」缩成「入 / 不入」两种。

与 bitmask 是一回事：这棵二叉决策树的每条根到叶路径，就是一串「入 / 不入」——正是 bitmask 里那个 0 / 1 向量。区别只在遍历次序：bitmask 按整数升序，递归按深度优先。产出的集合完全相同。

3 · 迭代级联：每读入一个元素，规模翻倍

cascade · {∅} 起步，逐元素翻倍

从只含空集的 {∅} 起步。每读入一个新元素 e，把当前已有的全部子集各复制一份、给副本加入 e，再并回集合——于是子集分成「不含 e」（原样）与「含 e」（新副本）两半。每读入一个元素规模翻倍，读完 n 个元素得到 ${2^n}$ 个子集。

无递归、无位运算：它只是反复「复制并追加」，自然生成也自然去重（新副本一定含 e，与旧的不重）。子集数 ${2^n = 2 \cdot 2 \cdot \dots \cdot 2}$ 的翻倍在这里看得最直白——每个元素给总量乘上一个 2。

4 · Gray code：相邻子集只差一个元素

Gray code · g = i ⊕ (i >> 1)

同样遍历 $i = 0 .. 2^n - 1$ ，但不直接用 i 的二进制，而是取 $g = i \oplus (i >> 1)$ 作为「选 / 不选」向量。二进制反射 Gray 码的性质是：相邻两个 g 恰好只差一个二进制位，于是相邻两个子集只差一个元素（加入或移出正好一个）。

为什么要「只差一个」：当子集上要维护的量可增量更新时（如子集和、子集异或），从上一个子集到下一个只需加入 / 移出一个元素，不必重算整份——Gray 码把每步的改动压到最小。它枚举的仍是那 ${2^n}$ 个子集，只是排成了「相邻仅一元素之差」的次序。

四法同源：四种算法产出的次序各不相同，但产出的集合完全一致——都是那 ${2^n}$ 个子集，不重不漏。其中 bitmask、逐元素递归、Gray code 本质都在枚举同一批「选 / 不选」的 0 / 1 向量，只是遍历次序不同；迭代级联则从空集出发逐元素翻倍。回到枚举划分的「含最小元素的块」：它每一步「给最小元素挑同伴」，正是枚举其余元素的一个子集——那一步用的就是这里的算法。

5 · 相关链接

Power set — P(A) · en.wikipedia.org——幂集、2^|A|，以及它作为一个集合「全部子集」的集合。
Gray code · en.wikipedia.org——二进制反射 Gray 码 $g = i \oplus (i >> 1)$ 、相邻只差一位的性质与典型应用。
Combination — C(n, k) · en.wikipedia.org——按大小 k 分层的子集即组合 C(n, k)，且 $Σ C(n, k) = 2^n$ 。