枚举子集的飘逸写法

要二进制枚举子集啦（准确地说是先枚举集合 S 再枚举 S 的子集 T），其中 S 最多有 n 个元素。

很容易想到，每个物体有取（1）和不取（0）两种情况，那么总共有 $2^n$ 种情况。
要一次概括所有物体的选择情况，二进制就是很好的选择。

CODE：

for (int i = 0; i < (1 << n); ++i) {  // i 枚举所有物体的选择情况
    for (int j = i; j; j = (j - 1) & i) {
        printf("%d %d\n", i, j);
    }
}

为什么第二层循环中是 j = (j - 1) & i 呢？
这样起到了将 j 中有效位（为1）逐渐删除的效果。
例如，当 i = 101000 时，j 初始为 101000，第一轮变为 100111，& i 后变为 100000，成功将最后一个1删除。

时间复杂度计算很玄学，可以发现 S 有 $\binom{n}{i}$ 种选法，i 个中还有 $2^i$ 种选取情况。
所以就是：

$$\sum_{i=0}^n{\binom{n}{i} * 2^i}$$

再通过某种玄学证明可得该式 = $3^n$。(20.02.07upd: 就是二项式定理啦！！！即 (1 + 2) ^ n)

同样的，若枚举 S 的子集 T，再枚举 T 的子集 T1，时间复杂度就是 $4^n$。

需要注意的是，O($3^n$) 表示 <= $3^n$，而 $3^n$ 就是 $3^n$，是一个准确值。

顺带的，若要枚举集合 U 中的子集 S 和 T，其中 S 与 T 无重复元素，只需枚举 S，再在 U 中除 S 的元素中枚举 T。

这是一种很好的二进制思想，利用位运算，巧妙地将冗余降到了最低，因此是最优的该类算法。尽管最优，因为是指数级算法，n 也只能最多取到15左右。