1. 什么是二进制枚举

我们学过 鸡兔同笼，学过 百鸡百钱，这类题目都是组合枚举。组合枚举有几个特点：

1. 有一些变量，变量的值不确定。例如，鸡兔同笼里，鸡的数量，兔的数量就是不确定的，百鸡百钱里面有 母鸡数量、公鸡数量、小鸡数量。这些变量的值是整条题的关键。

2. 变量之间是彼此有联系的，或者说要满足一些约束，例如，百鸡百钱，三种鸡的数量合起来是 100，所以，某一种多一些，其它两种自然就得少一些。另外，还要总价刚好等于 100，这也是一个约束条件。我们枚举几个变量的时候，需要一个个条件去检验。枚举其实就是把每一种可能的方案罗列出来，条件检验就是看罗列的这些方案是否满足题意，去伪存真。

说到这里，我们引入两个术语，一个是解，解就是满足题目条件的一种方案，第二个术语是解空间，解空间说的是真正的解存在于什么范围，枚举的时候是从什么范围去试。解是存在于解空间当中的，但是解空间里面的内容不都是解。

例如百鸡百钱里，解空间就是 所有(i,j,k) 1<=k<=100,1<=k<=100,1<=k<=100。我们暴力枚举的时候就是写三层循环，去一个个验证 i,j,k 。

在枚举类的题目里，有一类题目除了有上述的特点之外，还有一些额外的特点：

1. 变量的数量比较多（也不能太多，太多了这种算法就超时了，一般不超过 20 个 )

2. 每一个变量只有两种情况。

对应第一个特点，如果我们要写一个循环来枚举的话，那就要写 20 层了。这明显就是很不科学的。而且，有时候题目说的变量数还是不确定的，有可能是 20，有可能是 10，输入的数据决定了多少层。

有些同学会想到用 dfs 来解决这个问题，对，没错，dfs 是可以解决这个问题的。但是因为递归调用的效率不是太高，所以，能不用递归就不用递归，我们今天要学一个新方法。

我们尝试用一个数字去浓缩表达一个方案，所以，我们枚举解空间就是枚举一批数字，然后，再把数字拆分成具体的方案细节，再来验证是否是一个合法的解。

2. 例题

题目描述

给出长度为 N 的数组，求能否从中选出若干个，使他们的和为 K 。如果可以，,输出 Yes，否则输出 No。

输入格式

第 1 行，输入 N，K，为数组的长度和需要判断的和（2 ≤ N ≤20，1 ≤ K ≤10^9）

第 2 行，N 个值，表示数组中元素的值（1 ≤ a[i] ≤10^6）

输出格式

输出 Yes 或 No。

样例

5 13
2 4 6 8 10

No

2.1 题目分析

N 个数，选出一部分，让它们的和为 K。从暴力枚举的角度来看，就是写 N 层循环，每一层循环就是从 0 到 1，然后最终根据这 N 个循环变量来验证方案是否符合要求。如果第 i 层循环变量是 0，表示不选第 i 个数字，如果是 1，表示选这个数字。

因为 N 是不确定的，所以没办法直接写出 N 层循环（能写出来也很不美观，20 层循环，很难检查错误），所以，我们可以用 DFS 算法来实现这条题。

2.2 DFS 解题

#include<bits/stdc++.h>
using namespace std;
int n,k,x[21],a[21],ans;
bool Found;
void dfs(int l){
	if(l==n){
		int sum=0;
		for(int i=0;i<n;i++)
			sum += x[i]*a[i];
		if(sum==k)
			Found=true;
	}else{
		for(a[l]=0;a[l]<=1;a[l]++)
			dfs(l+1);
	}
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>x[i];
	
	dfs(0);
	
	if(Found) printf("Yes");
	else printf("No");

	return 0;
}

2.3 二进制枚举解题

上面这个程序写得一般般，但不妨碍我们基于这个 DFS 来思考 二进制枚举。这个 DFS 程序的 dfs 函数，是去枚举第 i 个数要还是不要，a[l] 为 0 表示 不要，为 1 表示不要。决定了第 l 个数要不要之后，就递归考虑要不要第 l+1 个数。当考虑到要不要第 n 个数的时候表示解空间的一个潜在方案已经构造出来（因为从 0 开始做下标，所以到 n 的时候表示考虑完了），就根据这个方案算出和，比较一下 k 。

我们现在要换一个思维，假设 n 为 5，那么:

全部数字都不加，就是 0,0,0,0,0

如果只加第 1 个数，其余 4 个数不加，那就是 0,0,0,0,1

如果只加第 2 个数，其余数不加，那就是 0,0,0,1,0

如果只加第 1 和第 2 个数，其余数不加，那就是 0,0,0,1,1

如果只加第 3 个数，其余数不加，那就是 0,0,1,0,0

如果只加第 1 和第 3 个数，其余数不加，那就是 0,0,1,0,1

.....

如果全部数都加，那就是 1,1,1,1,1

大家有没有看到，这其实就是一系列的二进制数，这个二进制数最小的是 $(00000)_2$，转成 10 进制数就是 0，最大的是 $(11111)_2$ ，转成十进制数就是 31 。所以，我们可以枚举 0 到 31 ，再来转换成二进制数，再来验证方案。基于这个思路，代码是

#include<bits/stdc++.h>
using namespace std;
int n,k,x[21],a[21],ans;
void change(int t){
	for(int i=0;i<n;i++){
		a[i] = t%2;
		t = t/2;
	}
}
bool check(){
	int sum=0;
	for(int i=0;i<n;i++)
		sum += a[i]*x[i];
	
	return sum == k;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>x[i];
	
	int MAX=1;
	for(int i=1;i<=n;i++) MAX *= 2;
	
	for(int i=1;i<MAX;i++){
		change(i);
		if(check()){
			printf("Yes");
			return 0;
		}
	}

	printf("No");

	return 0;
}

上面这个程序，有几个关键点：

1. 从 1 到 MAX 是解空间，这个 MAX 要会算。有 n 个数字，每个数字可以选，可以不选，那么就是有 $2^n$ 种方案，全部都选，就是 $2^n-1$，全部都不选就是 0

2. 本题 k 是正数，所以全部数字都不选是不需要枚举的，因此 change 函数的输入参数 t 一定是 正数。有一些题目，全部为 0 也是潜在解，那就不能用以前常用的 while(t) 循环来取二进制位（或者要先特判）

2.4 引入位运算的二进制枚举

到现在，二进制枚举的代码思路就出来了。但是，上面的二进制枚举的代码一般可以写得更漂亮一些。考试的时候，常常考。

==一个数是 t ，我们想知道它第 i 位是什么，可以通过 t& (1<<(i-1) ) 得知，如果这个运算的结果是 0 ，表示 t 的第 j 位是 0；如果 这个运算的结果非 0 ，表示 t 的第 j 位是 1 ==。

位运算符号中， & 的优先级高于 |，加减法的优先级也高于 移位运算符，所以请注意上面式子的括号。

因此，我们基于这个思路，改写上面的程序

#include<bits/stdc++.h>
using namespace std;
int n,k,x[21],a[21],ans;
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>x[i];
	
	int MAX= __填空(1)__ ; // 请基于 位运算 的思想填写
	
	int sum;
	for(int t=1;t<MAX;t++){
		__填空(2)__;
		for(int i=0;i<n;i++){
			if( __填空(3)__ )
				sum += __填空(4)__;
		}
		if(sum==k){
			printf("Yes");
			return 0;
		}
	}

	printf("No");

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}