子集生成 二进制表示

在集合表示法中， 1 << i 表示元素 i； S & (1<<j) 为真表示S和{j}的交集不为空，即S中含有j； S ^(1<<j)表示S中删除元素j。

#include <iostream>

using namespace std;

int n = 4;

void subset()
{
        for(int S = 0; S < (1<<n); S++)
        {
                cout << "S : " << S << " => ";
                for(int i = 0; i < n; i++)
                {
                        if(S & (1<<i))
                        {
                                cout << i << " ";
                        }
                }
                cout << endl;
        }
}

int main()
{
        subset();       
}

输出结果：

S : 0 => 
S : 1 => 0 
S : 2 => 1 
S : 3 => 0 1 
S : 4 => 2 
S : 5 => 0 2 
S : 6 => 1 2 
S : 7 => 0 1 2 
S : 8 => 3 
S : 9 => 0 3 
S : 10 => 1 3 
S : 11 => 0 1 3 
S : 12 => 2 3 
S : 13 => 0 2 3 
S : 14 => 1 2 3 
S : 15 => 0 1 2 3