在状态压缩中，有时会遇到集合间转移的题目，而如何找到某个集合的所有子集，成为了解决问题的关键。

首先，对于一个集合 \(s\)，我们可以通过它转换为二进制数后的 \(0\) 和 \(1\) 来表示一些元素的状态。如：选择和未选，经过与未经过。下文的集合均指其压缩后的二进制数。很显然，对于 \(s\) 的子集，它的大小不会超过 \(s\)。因为超过以后，意味着一定有一个不在 \(s\) 中的 \(1\)。所以，我们的枚举范围就缩小到所有小于等于 \(s\) 的数。假设我们枚举到了集合 \(x\)，判断 \(x\) 是否为 \(s\) 的一个子集最简单也是最暴力的方法：枚举 \(x\) 每一位，看是否有不在 \(s\) 中的元素。

但这样有个显然的问题，就是太慢了。有没有快一点的方法判断是否为子集呢？

答案是判断一下 \(x\) & \(s\) 是否等于 \(x\) 即可。为什么这样是对的呢？因为与操作可以将 \(x\) 中所有在 \(s\) 中为 \(0\) 的位置上的 \(1\) 抹去，而为 \(1\) 的位置上不变。

那么有

好，现在我们有了快速判断子集的方法！那么，我们以 \(s = 11010\) 为例，看一看枚举的效果——

怎么样，是不是不重不漏~

emm，但是你还是感觉太慢了。如果 \(s\) 太大，那枚举的次数可是 \(2^n\) 级别的！

我们发现，当我们枚举时，有很多冗余的状态——

我们发现，对于每一个合法的 \(x\)，它的下一个合法子集（设为 \(y\) )，总是小于 \(x\)，而中间的所有状态（设为 \(q\)）都满足 \(y < q < x\)，那我们不妨直接去生成这个 \(y\)。于是有 \(y = s\) & \((x-1)\)。

为什么这样是正确的呢？因为减去 \(1\) 会让 \(x\) 最后一个 \(1\) 变为 \(0\)，而它之后的所有位变成 \(1\)。与 \(s\) 做与运算后，相当于消去最后一个 \(1\)，然后再去枚举这个 \(1\) 之后的二进制数的子集。

可以发现，这样枚举也是不重不漏的。

输出如下——

这样子，枚举的复杂度就变为 \(2^k-1\) 了，其中 \(k\) 是集合中元素的数量。