python/TangDou/AcWing/DP/StateCompression/枚举一个集合的所有有效子集.md

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

/*
二进制数的“子集”
这里的“子集“指的是对于原二进制数中1的选择，如对于一个二进制数01101，有3个1，则有8个“子集”，分别为：00000,00001,00101,01000,01100,01001,00101,01101。
*/

//输出十进制对应的二进制数(模板)
void print(int n) {
    printf("%d:", n);
    //输出4个数位的二进制数
    for (int i = 3; i >= 0; i--) //由高到低位
        printf("%d", n >> i & 1);
    printf("\n");
}

//输出st的所有二进制子集
//一种是遍历所有情况，判断其是否为子集,如01101需要判断00000到01101。
void sub1(int st) {
    for (int i = st - 1; i; i--)
        if ((i & st) == i) {
            // i是state的 **子集**
            print(i);
        }
}

//一种很巧妙的方法：但我不会证明其正确性
void sub2(int st) {
    for (int i = st & (st - 1); i; i = (i - 1) & st) {
        // i是state的 **子集**
        print(i);
    }
}

int main() {
    int st = 13; // 01101
    sub1(st);
    printf("==================================\n");
    sub2(st);
    return 0;
}