#include<iostream>
#include<algorithm>
using namespace std;

    
int cas,m,data[20],i,j,k,sum,f,used[20];
int search(int realb,int begin,int end)
{
	if(data[begin]+data[end]>sum)
		return 0;
	
	int i;
	for(i=begin;i<end;i++)
	{ 
		if(used[i]==0)
	{
		if(data[i]+data[end]==sum)
		{
	used[i]=used[end]=1;
		f++;
		if(f==3)
			return 1;
int b=end;
		  while(used[b])
			  b--;

		  if(i==realb)
          {  
			  int t=i+1;
			  while(used[t])
				  t++;
		      if(search(t,t,b))
				  return 1;
			  f--;
               	used[i]=used[end]=0;

				return 0;
		  }
		  else
		  { 
			  if(search(realb,realb,b))
				  return 1;
			   f--;
               	used[i]=used[end]=0;
				return 0;
		  }

		 }
		}
	}
		
		
	
	int last,lastdata;
	last=lastdata=-1;
	
	for(i=begin;i<end;i++)
	{
	
		if(used[i]==0)
	{
		if(data[i]+data[end]<sum&&data[i]!=lastdata)
		{
	used[i]=1;
	data[end]+=data[i];
	     int a=i+1;
		 while(used[a])
			 a++;

	   if(i==realb)
	   {

		  if(search(a,a,end))
			  return 1;

		  lastdata=data[i];
 data[end]-=data[i];


		}
	   else
	   { 
 if(search(realb,a,end))
			  return 1;
		  lastdata=data[i];
 data[end]-=data[i];
	   }
	   used[i]=0;
	  

		if(data[i]+data[end]>sum)
			return 0;
	}
		}
	}
		return 0;
	}







int main()
{
	
	scanf("%d",&cas);
	for(i=1;i<=cas;i++)
	{
		cin>>m;
		sum=0;
		for(j=0;j<m;j++)
		{
			cin>>data[j];
			sum+=data[j];
		}
		if(m<=3||sum%4)
		{	printf("no\n");
		continue;
		}
		sum/=4;
		f=0;
		memset(used,0,sizeof(used));
       sort(data,data+m);
	   for(j=0;j<m;j++)
		   if(data[j]==sum)
		   {
			   f++;
			   used[j]=1;
		   }
		   if(f==3||f==4)
		   {  cout<<"yes\n";
		   continue;
		   }
		  int a=0,b=m-1;
		  while(used[a])
			  a++;
		  while(used[b])
			  b--;
		  if(search(a,a,b))
		  {
			  cout<<"yes\n";
		  }
		  else
			  printf("no\n");
	}
	return 0;
}

• 这么长.....也叫精简的啊、、、、、 (0) jdx2013519 2009-04-05 10:41:43
  • Re:这么长.....也叫精简的啊、、、、、 (6) lisp 2009-04-05 10:54:15
  • Re:这么长.....也叫精简的啊、、、、、 (15) sinianyizhan 2011-05-22 17:33:25