枚举一个集合的子集

打了个比赛没认真结果爆零QAQ,学到了QAQ。

对于我们在状压枚举枚举到的一个集合$S$,如何枚举它的子集$S’$???

code

1
2
3
4
5
for(int s=1;s<=1<<n;s++)
for(int s1=s;s>0;s=(s-1)&s)
{
//搞事
}

时间复杂度:$o(3^n)$

算法证明

其实对于一个集合$S=“100111”$,由于在二进制里,$0$是可以用来“传递”$1$的,所以用&运算来忽略掉集合$S$里面的$0$,把它变成$“1111”$,然后就可以不断减$1$,来达到枚举的效果。

时间证明

$\sum_{i=0}^n Cn^i\cdot2^i=\sum{i=0}^n C_n^i\cdot2^i\cdot1^{n-i}$

根据二项式定理(百度百科):$\sum_{i=0}^n C_n^i\cdot2^i\cdot1^{n-i}=(2+1)^n=3^n$