POJ 2362 - Square

//Memory Time 
//244K   79MS 

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

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

int n;  //木棒数量
int side;  //正方形边长
bool dfs(int* stick,bool* vist,int num,int len,int s)  //num:已组合的正方形的边数  len:当前组合的边已组合的长度,len<=side
{                                                      //s:stick[]的搜索起点
    if(num==3)   //剪枝3，当满足剪枝1和2的要求时，只需组合3条side，剩下的棒子必然能够组成最后一条side
        return true;

    for(int i=s;i<n;i++)
    {
        if(vist[i])
            continue;

        vist[i]=true;
        if(len+stick[i]<side)
        {
            if(dfs(stick,vist,num,len+stick[i],i))  //继续构建当前side
                return true;
        }
        else if(len+stick[i]==side)
        {
            if(dfs(stick,vist,num+1,0,0))  //构建新side
                return true;
        }
        vist[i]=false;
    }

    return false;
}

int main(void)
{
    int time;
    cin>>time;
    for(int t=0;t<time;t++)
    {    
        int sum=0;  //所有木棒长度之和

        cin>>n;
        int* stick=new int[n];
        bool* vist=new bool[n];

        for(int i=0;i<n;i++)
        {
            cin>>stick[i];
            vist[i]=false;

            sum+=stick[i];
        }        

        if(n<4 || sum%4!=0)    //剪枝1，不能构成正方形
        {
            cout<<"no"<<endl;
            continue;
        }

        qsort(stick,n,sizeof(int),cmp);   //降序排列，先组合长棒，因为长棒相对于短棒的组合灵活性较低

        side=sum/4;  //边长
        if(side<stick[0])   //剪枝2，side<max_stick
        {
            cout<<"no"<<endl;
            continue;
        }

        if(dfs(stick,vist,0,0,0))
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;

        delete stick;
        delete vist;
    }
    return 0;
}