枚举子集&高位前缀和

最近做的题里面有这个东西，于是写一篇博客总结一下吧。

枚举子集

枚举子集就是状压的时候枚举其中的二进制位中的1的子集。直接暴力枚举二进制位时间复杂度是\(O(4^n)\)，但是我们可以发现，对于每一位有以下三种状态，在枚举的子集中为1，在子集中为0且在原状态中为1，以及在原状态中为0。这样，对于1到\(2^n\)的数中，子集的总数为\(3^n\)，这样，通过一些比较优秀的枚举，时间复杂度即为\(O(3^n)\)。代码如下：

for(int i=s;;i=(i-1)&s) {
    //do sth...
    if(!i) break;
}

其中，对于每次循环的i，枚举的即是s的子集。

枚举子集&高位前缀和

原文：https://www.cnblogs.com/shanxieng/p/9813061.html