一.折半搜索

顾名思义，就是将搜索数据减为原先的一半，分两次搜。

原先复杂度 \(O(2^n)\)，优化成 \(O(2^{n/2})\)，非常可观。

但是分两次后应合并，一半难点在于如何合并。

例题：

luogu-P3067

思路：

对每个数，如果加入 A 集合，那么和加上这个数即可；加入 B 集合，在 A 集合中减去这个数即可；按兵不动，就啥也不干。

最后合并可以采取双指针，两边相加为 0 即可。

但是这样有可能会重复，我们可以用二进制数来表示每个位置选和不选的状态，最后在按位或比较一下即可。

注意有可能产奶量相同而奶牛不同，所以在前后相同时，应该将右指针回到原来位置。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define ll long long

using namespace std;

int n, a[28];

ll ans;

bool vis[1 << 21];

struct node {
	int x, f;
};

node suml[1 << 21], sumr[1 << 21];

int cntl, cntr;

inline bool cmpl(node a1, node b1) {
	return a1.x < b1.x; 
}

inline bool cmpr(node a1, node b1) {
	return a1.x > b1.x;
}

void dfs(int l, int r, node sum[], int &num, int addx, int addf) {
	if (l > r) {
		sum[++ num] = (node) {addx, addf};
		return ;
	}
	
	dfs(l + 1, r, sum, num, addx + a[l], addf + (1 << (l - 1)));
	dfs(l + 1, r, sum, num, addx - a[l], addf + (1 << (l - 1)));
	dfs(l + 1, r, sum, num, addx, addf);
}

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i ++)
		scanf("%d", &a[i]);
	
	int mid = n >> 1;
	
	dfs(1, mid, suml, cntl, 0, 0);
	dfs(mid + 1, n, sumr, cntr, 0, 0);
	
	sort(suml + 1, suml + 1 + cntl, cmpl);
	sort(sumr + 1, sumr + 1 + cntr, cmpr);
	
	int i = 1, j = 1;
	
	while (i <= cntl && j <= cntr) {
		while (sumr[j].x + suml[i].x > 0 && j <= cntr) j ++;
		
		int pos = j; 
		
		while (j <= cntr && sumr[j].x + suml[i].x == 0) {
			int tmp = sumr[j].f | suml[i].f; 
			
			if (! vis[tmp]) {
				vis[tmp] = 1;
				ans ++;
			}
			
			j ++;
		}
		
		if (i < cntl && suml[i].x == suml[i + 1].x) j = pos;
		
		i ++;
	}
	
	printf("%lld\n", ans - 1);
	
	return 0;
}

二.A*