2362.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 94 行

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 23
int b[NMAX],v[NMAX],n,sum;
int cmp(const void *a,const void *b)
{
	return (*(int*)b)-(*(int*)a);
}
int flag=1,m[5];
int tr(int k,int last,int s);
int judge(int s)
{
	int i;
	if(s==4)
		return 1;
	for(i=0;i<n;i++)
	{
		if(!v[i])
			break;
	}
	return tr(i,sum/4,s);
}
int tr(int k,int last,int s)
{
	int i;
	for(i=k;i<n;i++)
	{
		if(v[i])
			continue;
		if(last-b[i]>=0)
		{
			v[i]=1;
			if(last-b[i]==0)
			{
				if(judge(s+1))
					return 1;
				
			}
			else
			{
				if(tr(i+1,last-b[i],s))
					return 1;
			}
			v[i]=0;
		}
	}
	return 0;
}

main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&b[i]);
			sum+=b[i];
		}
		if(sum%4)
		{
			printf("no\n");
			continue;
		}
		qsort(b,n,sizeof(int),cmp);
		memset(v,0,sizeof(v));
		memset(m,0,sizeof(m));
		m[1]=0;
		if(judge(1))
			printf("yes\n");
		else
			printf("no\n");
	}

#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}