二进制枚举

让我们从一个题目入手

从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。

关于这个题目，我们很容易想到的便是对所有元素进行暴力搜索，然后进行剪枝便可。

下面我将介绍二进制枚举的思路和流程来巧妙的解决这个问题。

对任一数来说，所面临的问题是取或不取，在二进制中便可以用1或0来表示。由于每个数都会对应一串二进制数字，那么结果便有2^{n个状态，如1000001便相对于取0号位元素和最后一号元素，其他元素不取。那么我们可以枚举这2}n个状态，通过遍历当前状态的每一位来判断，然后对取的元素求和判断是否为一个合格的状态。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int maxn = 2005;
int a[maxn], n, t, cnt;
int main()
{
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	cin >> t;
	for(int i = 1; i < (1 << n); i++)
    {
        int sum = 0;//元素和
        for(int j = 0; j < n; j++)
        {
            if(i & (1 << j))//判断当前状态i的二进制数第j位是否为1，取或不取
                sum += a[j];
        }
        if(sum == t)//满足条件记录
        {
            for(int j = 0; j < n; j++)
            {
                if(i & (1 << j))
                    cout << a[j] << " ";
            }
            cout << endl;
            cnt++;//记录合理数
        }
    }
    cout << cnt << endl;
}

看完上面代码，有些小伙伴就要问了，i&(1<<j)是什么。

那么补充一波位运算的知识吧：

按位与运算符（&）

参加运算的两个数据，按二进制位进行“与”运算。

运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;

即：两位同时为“1”，结果才为“1”，否则为0

例如：3&5 即 0000 0011& 00000101 = 00000001 因此，3&5的值得1。

左移运算（<<）

a << b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 << 2 = 400。可以看出，a << b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2(这样做要求保证高位的1不被移出)。
通常认为a << 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。注意:不要用于浮点数类型

最后，给出二进制的基本模板

  	for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
    {
        for(int j = 0; j < n; j++) //遍历二进制的每一位
        {
            if(i & (1 << j))//判断二进制第j位是否存在
            {
                //进行操作
            }
        }
        printf("
");
    }