10364

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

#define ll long long

using namespace std;

int sz[25];
ll sum;
bool f;
int total_piece;
int stick_size;
bool visit[25];
int M;

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

bool backtrack(int present_size,int index,int piece_cnt)
{
	if(stick_size*piece_cnt==sum)
		return 1;
	for(int i=index;i<M;i++)
	{
		if(visit[i])
		continue;
		if(i>0 && !visit[i-1] && sz[i]==sz[i-1])
		continue;

		if(present_size+sz[i]==stick_size)
		{
			visit[i]=1;
			if(backtrack(0,0,piece_cnt+1))
			return 1;
			visit[i]=0;
			return 0;
		}
		else if(present_size+sz[i]<stick_size)
		{
			visit[i]=1;
			if(backtrack(present_size+sz[i],i+1,piece_cnt))
			return 1;
			visit[i]=0;
			if(present_size==0)
			return 0;
		}
	}
	return 0;
}

int main()
{
	int t;
	int mx_sz;
	cin>>t;

	while(t--)
	{
		cin>>M;
		mx_sz = 0;
		sum = 0;
		for(int i=0;i<M;i++)
		{
			cin>>sz[i];
			sum+=sz[i];
			if(sz[i]>mx_sz)
				mx_sz = sz[i];
		}
		if(sum%4)
		{
			cout<<"no\n";
			continue;
		}
		if(mx_sz>sum/4)
		{
			cout<<"no\n";
			continue;
		}
		sort(sz,sz+M,cmp);
		memset(visit,0,sizeof(visit));
		stick_size = sum/4;
		if(backtrack(0,0,0))
		cout<<"yes\n";
		else
		cout<<"no\n";
	}

	return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *