暴力求解法(三)—利用二进制法来枚举集合的子集

  给定一个集合，枚举所有该集合的子集，包括空集在内总共2^n个子集。

  求集合的子集的方法有三种：1.增量构造法。2.位向量法。3.二进制法（推荐）。

  二进制法求集合的子集:

  基础知识:1.常见的集合运算都可以位运算符完成，常见的位运算符是与&，或|，非！，异或^(当且仅当二者不同时为真)，他们和对应的逻辑运算非常相似。

                          1011 & 1100 = 1000   对应集合取叫集

                          1011 |  1100 =  1111   对应集合取并集

                          1011 ^ 1100 =  0111   对应集合取对称差

                  2.左移<<和右移>>的意义:         a.   101<<2 = 10100（101左移两位)  等价于  5×2×2 = 20。

                                                                    b.   101>>2 = 1(101右移两位)  等价于  5÷2÷2 = 1（向下整除)。

  二进制法详解:任何集合都可以化为S={0,1,2,3.......,n}，为什么呢？原因很简单，可以将集合存入一个数组，则下标就对应一个元素。

  对于集合S={0,1,2,3......,n},我们另某一个二进制数对于某个子集，则该二进制数满足以下的特点：从左到右第i位表示元素i是否在子集中，1表示在，0表示不在。

  对于一个代表某一个子集二进制数，如何判断集合中的各个元素在不在？:

  我们可以用&运算发解决该问题,详细规律请看表。

  解决完上述问题，我们就不难写出代码了。

  二进制法求子集代码展示:

#include<bits/stdc++.h>
using namespace std;
int n;
vector<char>al;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        char ch;
        cin>>ch;
        if(ch!=‘\n‘){
            al.push_back(ch);
        }
    }
    for(int i=0;i<(1<<al.size());i++){  //上限为 1<<al.size()
        for(int j=0;j<al.size();j++){
            if(i&(1<<j)){    //注意这里不要写成了 && 
                cout<<al[j]<<‘ ‘;
            }
        }
        cout<<endl;
    }
}

  输入输出样例:

输入:
5
a b c d e
输出:
   （这一行为空集)
a     
b     
a b   
c     
a c   
b c   
a b c 
d     
a d   
b d   
a c d
b c d
a b c d
e
a e
b e
a b e
c e
a c e
b c e
a b c e
d e
a d e
b d e
a b d e
c d e
a c d e
b c d e
a b c d e   

暴力求解法(三)—利用二进制法来枚举集合的子集

原文：https://www.cnblogs.com/acmerhome/p/14790125.html