子集枚举

一句话理解

子集枚举还可以枚举一个集合的所有子集合。

为什么要学

状压 DP 的常见内层。

讲解

for (int sub=s; sub; sub=(sub-1)&s) 枚举 s 的非空子集。再处理空集。

3^n 的 SOS、子集 DP 会用到。

例子

s=1011₂，会依次得到 1011、1010、1001、1000、0011、0010、0001。

常见错误

• 写成 sub— 会跑出集合。
• 死循环：sub=0 还继续 (sub-1)&s。