枚举子集

Part I. 概念

一个二进制状态，第 \(i\) 为 \(1\) 表示 \(i\) 在集合中，反之为不在集合中，求这个集合所有子集（可以为空）的二进制状态。

例如 \(1101\) 的所有子集为 \(0000,0001,0100,0101,1000,1001,1100,1101\)。

常用作状压 dp。

Part II. 怎么求

（假设要枚举的二进制串为 \(s\)）

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

Part III. 性质

假设一个数 \(x\) 的子集数量为 \(f(x)\)，那么：

证明：（https://www.acwing.com/community/content/513/）

若 \(x\) 二下有 \(k\) 个 \(1\)，那么显然 \(\mathcal O(f(x))=\mathcal O(2^k)\)。\([1,2^n)\) 中恰好 \(1\) 位二进制的有 \(\mathcal O(\mathrm C_n^1)\) 个，\(2\) 位有 \(\mathcal O(\mathrm C_n^2)\) 个，以此类推，可以得到：

一般用来计算复杂度。

枚举子集

原文：https://www.cnblogs.com/juruo-zzt/p/14551815.html