二进制

枚举子集

复杂度 (O(子集个数))

for (int i = S; i != 0; i = (i - 1) & S) ;

首先& S可以保证一定是子集

怎么证明一定全部会枚举到呢?

因为(-1)会将最小的(1)位变成(0), 更小的位全部变成(1), 因为是最小的(1), 所以接下来第一个 十进制数值 更小的子集肯定这一位是(0)了, 这样就可以调到接下来那个子集

枚举子集的子集

复杂度 (O(3 ^ n))

for (S in ((1 << n) - 1))
{
    for (T in S)
    {
        ...
    }
}

直观可以得到一个较松的上界 (O(4 ^ n))
其实对于一个 １ 元素有 (x) 个的集合, 他的子集有 (2 ^ x) 个, 而这样大小为 (x) 的集合是 (inom{n}{x}) 个
容易得到:

[sum_{x} inom{n}{x} cdot 2 ^ x ]

由二项式定理

[(1 + x) ^ n = sum_{i} inom{n}{i} cdot x ^ i ]

可得

在上式中带入 (x = 2), 结果 (= (1 + 2) ^ n = 3 ^ n)