HDU 1518 Square （DFS）

//题意不会度娘
           

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
bool visit[25];
int a[25];
int sum;
int n,k;
bool cmp(int a,int b)
{
	return a>b;
}
bool DFS(int we,int rng,int edg)//we为已经拼好的边，rng为第几根，edg为下一根棍子剩余的长度 
{
	if(we==3)
		return true;//如果数据能进DFS循环，则说明拼好第三条边时必能拼好第四条边 
	for(int i=rng;i<n;i++)//边逐一相加 
	{
		if(visit[i])
			continue;//如果边已经使用过 
		visit[i]=true;//标为已经使用 
		if(a[i]==edg)//凑好一条边的剩余长度刚好为这条边的长度 
		{
			if(DFS(we+1,0,k))//边数加一，已用的边数变为一，剩余长度重新标为k	
				return true;
		}
		else if(a[i]<edg)
		{
			if(DFS(we,i+1,edg-a[i]))//剩余的长度减去加上的a[i]长度 
				return true;
		}
		visit[i]=false;//都不符合则重新标为未使用 
	}	 
	return false;//无结果 
}
int main(int argc, char *argv[])
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		sum=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
		}
		k=sum/4; 
		if(sum%4!=0)//如果边数总长度不能被4整除，则必定为no 
		{
			printf("no\n");
			continue;
		}
		memset(visit,false,sizeof(visit));
		sort(a,a+n,cmp);
		if(DFS(0,0,k))
			printf("yes\n");
		else
			printf("no\n");
	}	
	return 0;
}
           

//start-ZJ
           

//2017/10/17/19:34