poj 2362 Square

#include <iostream>            //参照poj 1011 sticks

#include <algorithm>

using namespace std;

int sticks[20],visited[20];

int flag,total;

int t,seg;

int cmp(const void* a,const void* b)

{ 

return (*(const int*)b)-(*(const int *)a);

}

void solve(int k,int sum,int cnt)   

{ 

if(cnt==4)

        flag=true;

else if(sum==seg)

        solve(0,0,cnt+1);        

else    

for (int pre=-1,i=k;i<t;++i)    

if(visited[i]!=1&&sticks[i]!=pre&&sticks[i]+sum<=seg)        

            { 

                pre=sticks[i];

                visited[i]=1;

                solve(i+1,sum+sticks[i],cnt);    

                visited[i]=0;        



if(k==0||flag==1)return;    

            }

}

int main()

{ 

int c,i;

    scanf("%d",&c);

while(c--)

    { 

        total=0;

        flag=0;

        scanf("%d",&t);

for (i=0;i<t;++i)

        { 

            scanf("%d",&sticks[i]);

            total+=sticks[i];      

        }



        qsort(sticks,t,sizeof(sticks[0]),cmp);            

if(total%4!=0||sticks[0]>total/4)

            printf("no
");

else

        { 

            seg=total/4;

            memset(visited,0,sizeof(visited));

            solve(0,0,0);

if(flag)

                printf("yes
");

else

                printf("no
");

        }

    }

return 0;

}