有一个集合，请输出它的所有子集。
子集，即为被这个这个集合包括的所有集合，包括空集。那么显然，假如有 \(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，我们按照循环顺序模拟过程。
\(【1】1101\)
\(【2】1100\)
\(【3】1001\)
\(【4】1000\)
\(【5】0101\)
\(【6】0100\)
\(【7】0001\)
我们假定 \(0000\) 也在元素中，然后按照一定规律排列子集：
\[【1】1101\;\;\; 【5】0101 \]\[【2】1100\;\;\; 【6】0100 \]\[【3】1001\;\;\; 【7】0001 \]\[【4】1000\;\;\; 【8】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\) 。复杂度还算是比较优秀的。