pku2362 Square

#include<stdio.h>
#include<algorithm>

const int MAX=25;
int g[MAX];
bool visit[MAX];
bool exist;
int edge,n;

void dfs(int pos,int curLen,int depth)            
{
    if(depth==4)
    {
        exist=true;
        return ;
    }
    
    int pre=-1;        //避免重复搜索已不可利用的长度

    for(int i=pos;i<n;i++)
    {
        if(!visit[i]&&g[i]!=pre&&g[i]+curLen<=edge)
        {
            pre=g[i];                
            visit[i]=1;

            if(curLen+g[i]==edge) dfs(0,0,depth+1);        //首先整合剩余未用木棍中最长的木棍

            else dfs(i+1,curLen+g[i],depth);            
                                            
            visit[i]=0;        //回溯凑一个边的零头

            if(pos==0||exist) return;
        }
    }
}

int cmp(const void *a,const void *b)
{
    return *(int*)b-*(int*)a;
}

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        int sum=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&g[i]);
            visit[i]=0;
            sum+=g[i];
        }
        qsort(g,n,sizeof(int),cmp);     //将棍长从大到小排序

        if(sum%4==0&&g[0]<=(edge=sum/4))    //最长的棍长必须<=正方形的边长

        {
            exist=false;
            dfs(0,0,0);
            if(exist) printf("yes\n");
            else printf("no\n");
        }
        else printf("no\n");
    }
    return 0;
}