UVa 10364 - Square

// UVa 10364 - Square

#include <iostream>
#include <string.h>
using namespace std;

int n, a[20], pos[3][1048577], m;

void comb(int k, int mask, int sum) {
	if (sum >= m || k == n) {
		if (sum == m)
			pos[1][++pos[1][0]] = mask;
		return;
	}
	comb(k + 1, mask, sum);
	comb(k + 1, mask | (1 << k), sum + a[k]);
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		cin >> n;
		m = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			m += a[i];
		}
		bool sol = false;
		if (m % 4 == 0) {
			m /= 4;

			pos[1][0] = 0;
			comb(0, 0, 0);

			bool yet[1048576];
			memset(yet, true, sizeof(yet));
			// generate 2nd level
			pos[2][0] = 0;
			for (int i = 1; i < pos[1][0]; i++)
				for (int j = i + 1; j <= pos[1][0]; j++)
					if ((pos[1][i] & pos[1][j]) == 0 && yet[pos[1][i] | pos[1][j]]) {
						pos[2][++pos[2][0]] = pos[1][i] | pos[1][j];
						yet[pos[2][pos[2][0]]] = false;
					}
			// generate 3rd level
			for (int i = 1; i < pos[1][0] && !sol; i++)
				for (int j = 1; j <= pos[2][0]; j++)
					if ((pos[1][i] & pos[2][j]) == 0 && yet[pos[1][i] | pos[2][j]]) {
						int now = pos[1][i] | pos[2][j];
						yet[now] = false;
						sol = true;
						break;
					}
		}
		// output
		if (sol)
			cout << "yes" << endl;
		else
			cout << "no" << endl;
	}
	return 0;
}