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

本文共计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，我们按照循环顺序模拟过程。