枚举一个集合的子集

发表于 | 分类于 |

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

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

code

1
2
3
4
5
for(int s=1;s<=1<<n;s++)
  for(int s1=s;s1>0;s1=(s1-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$