子集问题

Posted on | In ,

子集的子集

枚举子集的子集是在2018CCPC秦皇岛接触到的。

以下摘抄ybmj

子集枚举

对全集$S$的每个子集$K$,进行子集的枚举

复杂度:$O(3^n)$

1
2
3
4
5
6
7
for (int i = 1; i < (1 << n); i++) {
    for (int j = i; j; j = (j - 1) & i) {
        /*
            j为i的子集
        */
    }
}

证明：

设全集有$n$个元素。

对于一个含有$k$个元素的集合来说，它的方案有$C^k_n$。每个集合的子集有$2^k$

所以对所有含有$k$个元素的集合，它的总子集数为$C^k_n \times 2^k$

那么对全集的每个子集进行子集枚举的复杂度为$\sum_{k=1}^{n} C^k_n \times 2^k$

由二项式定理$(x+y)^n = \sum_{k=0}^{n} x ^ k y ^ {n-k}$

所以子集枚举的复杂度为$(2+1)^n = 3^n$

复杂度:$O(n2^n)$

1
2
3
4
5
6
7
8
9
for (int i = 0; i < n; i++) {
    for (int j = 0; j < (1 << n); j++) {
        if (j & (1 << i)) {
        /*
            j ^ (1 << i) 为 j 的子集
        */
        }
    }
}