如何通过学习笔记掌握集合枚举子集的技巧？

本文共计1007个文字，预计阅读时间需要5分钟。

集合枚举子集-学习笔记算法+有一个集合，请输出它的所有子集。子集，即这个集合包含的所有集合，包括空集。显然，如果有\( n \)个元素，那么有\( 2^n \)个子集。如何枚举子集？

集合枚举子集-学习笔记 算法

有一个集合，请输出它的所有子集。

子集，即为被这个这个集合包括的所有集合，包括空集。那么显然，假如有 \(n\) 个元素，那么有 \(2^n\) 个子集。如何枚举子集呢？

首先有一个显然的方法：用 \(2^n\) 的 dfs 枚举。但这样有弊端：时空较大，而且比较麻烦。比如一个动态规划，你每次转移都要跑一遍 dfs ，时空开销很大，而且处理不方便。那么就有另外一种方法出现：循环枚举。

首先放代码：

for(int j=st;j;j=(j-1)&st) j2=st^j;

st 就是要枚举的集合，j 就是子集，j2 就是 j 相对于 st 的补集。这里我们认为集合是一个二进制数中所有元素 \(1\) ，一个 \(1\) 代表一个元素。这样为什么是正确的呢？

首先，为了保证枚举出来的元素都是原式的子集，我们用了 &st 这个位运算操作，因此可以保证。

其次，因为减法和按位与都是不增操作，因此可以保证不重。

那如何保证不漏呢？

模拟一遍过程：st =1101，我们按照循环顺序模拟过程。

\(1101\)​

\(1100\)

\(1001\)

\(1000\)

\(0101\)

\(0100\)

\(0001\)

我们假定 \(0000\) 也在元素中，然后按照一定规律排列子集：

\[1101\;\;\; 0101 \]

\[1100\;\;\; 0100 \]

\[1001\;\;\; 0001 \]

\[1000\;\;\; 0000 \]

有没有发现规律？每一行，后三位都是相同的。所以这个算法的本质算是，对于每一个 \(1\) ，先把这一位设定为 \(1\) 枚举后面所有位，再把这一位设定为 \(0\) 枚举一遍，然后再往前面递归。因为减 \(1\) 可以看做把最后一个 \(1\) 设定为 \(0\) ，后面所有设定为 \(1\)。这里建议还是自己手玩一下，找一找规律。所以这个算法类似于二进制枚举，考虑到了所有情况。

这个做法是从大到小枚举子集，着实十分优美。但要注意的是这种办法没法枚举空集，需要手动计算。

枚举子集在一些位运算的题目中可能会涉及，而这种方法可以很好地减少代码复杂度以及时空复杂度，同时也是一种很好的思想。

复杂度证明

空间不管。

时间的话，如果一个集合元素个数为 \(x\) ，复杂度为 \(O(2^x)\)。

有一种特殊情况：枚举 \(0\) 到 \(2^n-1\) 的所有数的所有子集，此时复杂度即为：

\[\sum_{k=0}^nC_n^k\times 2^k \]

相当于从 \(n\) 个位上选出 \(k\) 个位有值，然后有 \(C_n^k\) 种方案，每种方案 \(2^k\) 。

根据二项式定理：

\[(a+b)^n=\sum_{i=0}^nC_n^ia^ib^{n-i} \]

可得：原式等价于：

\[\sum_{k=0}^nC_n^k\times1^{n-k}\times2^k \]

等价于 \(3^n\) 。复杂度还算是比较优秀的。