子集dp

子集枚举

对全集$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} C_n^{k} 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 的子集
*/
}
}
}