子集枚举

子集枚举

给定一个由 $n$ 个不同的数构成的集合，求出这个集合所有的子集。

容易知道的是，对于每个数来说，有选或不选两种情况，故一共有 $2^n$ 个子集。

如此，这个 $n$ 一定不能太大，否则我们没办法枚举出所有的子集。

常见的方式是，用一个长度为 $n$ 的全 $1$ 的二进制数表示一个集合中的所有的数。

考虑为什么不能按 lowbit 来做，其实是可以的，但是其实指令次数更多，因为你要加，你要减

对于一个数 $m$，其二进制位中最低的 $1$ 为 $k$。

令 $s = m$，

$s-1$ 就是将 $[0,k-1]$ 这 $k$ 位设置为 $1$，$k$ 这位设置为 $0$，其余位仍为 $s$ 中对应的位。

然后 (s-1) & m 就是将 $s$ 中最低位 $k$ 删除，由于二进制的性质，再加上原本比 $k$ 更低的一些为 $1$ 的位即是最新的子集。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void print_subset(int m) {
    for (int s = m; s > 0; s = (s - 1) & m) {
        printf("%d\n", i);
    }
}

void print_subset_include_zero(int m) {
    for (int s = m; ; s = (s - 1) & m) {
        printf("%d\n", i);
        if (s == 0) break;
    }
}

时间复杂度分析

由于遍历只会枚举每个子集，二进制中 $1$ 的数量为 $count$ ，则时间复杂度为 $O(2^{count})$

拓展1

对于一个至多有 $n$ 个数的集合 $set$，考虑这个集合的每个子集，会作为多少其他集合的子集？

对应一个子集 $subset$，选择集合 $set$ 中不为子集的 $subset$ 的子集 $sb$，即 $sb \cup subset=set, sb\cap subset = \emptyset$。

那么枚举 $sb$ 的所有子集，与 $subset$ 取并后的结果就是 包含 $subset$ 的所有 $set$ 的子集。

时间复杂度仍为指数级

拓展2

遍历所有掩码的子掩码

1
2

for (int m = 0; m < (1 << n; ++i))
    for (int s = m; s; s = (s - 1 & m))

时间复杂度分析，对于每位有三种情况，

1. 如果掩码该位为0，则子掩码该位为0
2. 如果掩码该位为1，则子掩码该位可能为0，可能为1

故一共每位有三种情况，总共是 $O(3^n)$ 的复杂度。

另一种分析方式为，对于每个有 $k$ 个二进制位的掩码，一共有 $2^k$ 个子掩码，而一共有 $C(n,k)$ 个掩码的二进制位 $1$ 个数为 $k$。故总和为：$\sum\limits_{i=1}^nC_n^k 2^k$，根据二项式定理 $(a+b)^n=\sum\limits_{k=1}^n C_n^k a^k b^{n-k}$，令 $a=2,b=1$，总和为 $O(3^n)$

例题

1. 1494. 并行课程 II
2. 982. 按位与为零的三元组

参考

二进制集合操作