子集枚举

两个问题：

1. 有 \(n\) 个元素的集合，枚举其子集
2. 对于该子集，枚举其子集

Step 1 枚举有 \(n\) 个元素的集合 \(N\) 的子集¶

我们用二进制数来表示某一个元素取或不取，以此构成一个集合。

从全1到全0，一共 \(2^n\) 个。

1

for (int S = 0; S < (1 << n); S++)

状压dp经常用，这玩意儿是基础款 枚举子集

我们称 \(S\) 这个 \(n\) 位二进制数为一个状态

Step 2 枚举 \(S\)（即 \(N\) 的一个子集）的所有子集¶

由于不方便确定 \(S\) 中由1选中的 \(k\) 个元素，来重新建立一个\(2^k\)枚举。因此我们考虑对这个状态 \(S\) 做手脚。

于是有，枚举子集：

1
2
3

for (int T = S; T; T = (T - 1) & T) {
  // 每轮循环中的T即为S的子集
}

真子集：

1
2
3

for (int T=(S-1)&S; T; T=(T-1)&S){
  // 每轮循环中的T即为S的真子集
}

注意 \(T\) 的大小，其枚举的顺序与 \(S\) 相反，是 逆序

关于二进制枚举集合 - 知乎

同样的，其时间复杂度为 \(O(2^{\text{popcount}(S)})\)，下证：加上外面总复杂度 \(O(3^n)\)。

Step 3 两层结合即可 复杂度证明¶

关于时间复杂度的证明：https://www.cnblogs.com/CDOI-24374/p/15876755.html

我们不妨考虑按集合的大小 \(i\) 来枚举第一层子集：\(\sum \limits_{i = 0}^n C^i_n = 2^n\)

对于含有\(i\)个元素的子集，枚举有：\(2^i\)

结合一下，有\(\sum \limits_{i = 0}^n C^i_n 2^i\)，也即：

\(\sum \limits_{i = 0}^n C^i_n 2^i*1^{n-i}\)

使用二项式定理：

\((a+b)^n = \sum \limits_{i = 0}^ n C^i_n a^i b^{n - i}\)

比较得，\(a=2,b=1\) 的时候 \(3^n = \sum \limits_{i = 0}^n C^i_n 2^i\)。因此是 \(O(3^n)\) 的。