SP11469（折半搜索）

题目大意：

给出 $N$ 个数，求可以被分成两个和相等的集合的子集数。

思路分析：

首先考虑朴素的 DFS，每个数有三种情况：选为 $A$ 集合，选为 $B$ 集合，两个集合都不选。暴力 DFS 时间复杂度为 $3^{20}$。

观察到 $N$ 很小，而 $3^{10}$ 是可以通过本题的，于是考虑折半搜索。

我们设前半部分搜索出来的两个集合和分别为 $A$、$B$，后半部分为 $D$、$C$，则 $A+D=B+C$。

变形可得 $A-B=C-D$。

所以我们只需要记录当前 DFS 搜出来的两个集合差为多少。

part1. 第一遍 DFS

首先 DFS 从 $1$ 到 $(1+N)\div 2$，记录当前搜出来两个集合的差，同时用状态压缩记录选了哪些数。搜完后用 vector 记录当前状态。

由于差可能很大或为负数，我们需要用 map 编号（也就是离散化）后加入 vector。

part2. 第二遍 DFS

和第一遍相似，DFS 从 $(1+N)\div 2 +1$ 到 $N$，记录的内容和第一遍相同。

搜完后在 vector 的对应位置记录答案。

DFS 代码：

void dfs(int a,int b,int c,int d){//a表示当前位置，b表示结束位置，c表示搜索出来的差，d表示状压后的状态
	if(a==b+1){
		if(a!=n+1){//第一遍 DFS 后记录答案
			if(!m[c])  m[c]=++p;
			v[m[c]].push_back(d);
		}
		else{//第二遍 DFS 后记录答案
			int t=m[c];
			for(auto i:v[t])
				vis[i|d]=1;
		}
		return ;
	}
	dfs(a+1,b,c,d);//枚举三种情况
	dfs(a+1,b,c+A[a],d|(1<<a));
	dfs(a+1,b,c-A[a],d|(1<<a));
}

part3. 计算答案

这部分比较简单，枚举 vis 数组中所有状态记录答案。

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n,A[25],p,ans;
bool vis[2100000];
map<int,int> m;
vector<int> v[2100000];
void dfs(int a,int b,int c,int d){//a表示当前位置，b表示结束位置，c表示搜索出来的差，d表示状压后的状态
	if(a==b+1){
		if(a!=n+1){//第一遍 DFS 后记录答案
			if(!m[c])  m[c]=++p;
			v[m[c]].push_back(d);
		}
		else{//第二遍 DFS 后记录答案
			int t=m[c];
			for(auto i:v[t])
				vis[i|d]=1;
		}
		return ;
	}
	dfs(a+1,b,c,d);//枚举三种情况
	dfs(a+1,b,c+A[a],d|(1<<a));
	dfs(a+1,b,c-A[a],d|(1<<a));
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&A[i]);
	int mid=(1+n)>>1;
	dfs(1,mid,0,0);//第一次搜索
	dfs(mid+1,n,0,0);//第二次搜索
	for(int i=1;i<=(1<<n+1);i++)
		ans+=vis[i];//计算答案
	printf("%d",ans);
	return 0;
}