10364 - Square

10364 - Square.cpp

/**
 * Tittle:	10364 - Square
 * Author:	Cheng-Shih, Wong
 * Date:	2015/07/10
 */

// include files
#include <bits/stdc++.h>

using namespace std;

// definitions
#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
#define clr(x,v) memset( x, v, sizeof(x) )
#define N 25

typedef vector< int > VI;

// declarations
int n, t;
bool used[N];
int sum, tLen;
VI sticks;

// functions
bool cmp( int a, int b )
{
	return a > b;
}

void init()
{
	int val;
	clr( used, false );
	sticks.clear();
	cin >> n;
	sum = 0;
	FOR( i, 1, n ) {
		cin >> val;
		sum += val;
		sticks.push_back(val);
	}
	sort( sticks.begin(), sticks.end(), cmp );
	tLen = sum/4;
}

bool dfs( int sum, int layer, int idx )
{
	if( layer==3 ) return true;

	FOR( i, idx, sticks.size()-1 ) if( !used[i] ) {
		if( i>0 && !used[i-1] && sticks[i]==sticks[i-1] ) continue;
		if( sum+sticks[i] > tLen ) continue;
		
		used[i] = true;

		if( sum+sticks[i]==tLen ) {
			if( dfs( 0, layer+1, 0 ) ) return true;
		} else {
			if( dfs( sum+sticks[i], layer, i+1 ) ) return true;
		}

		used[i] = false;
		
		if( sum==0 ) return false;
	}
	return false;
}

bool check()
{
	if( sum%4 != 0 ) return false;
	for( int len:sticks )
		if( len > tLen ) return false;
	
	return dfs( 0, 0, 0 );
}

// main function
int main( void )
{
	
	// input
	cin >> t;

	while( t-- ) {
		init();
		
		if( check() ) puts("yes");
		else puts("no");
	}
	
	return 0;
}