例题9.4Square

//DFS好像不能是void函数
//没什么好说的，上代码

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int totallen;
int m;//棒子个数
int stick[21];
bool visit[21];
bool cmp(int a,int b)
{
    return a>b;
}
bool DFS(int sum,int number,int position)
{
    if(number==3)
    {
        //cout<<&quot;yes&quot;<<endl;
        return true;
    }
   // int sample=0;//不可能的重复边

   
    for(int i=position;i<=m;i++)
    {
        int nsum=sum+stick[i];
        
       // if(nsum>totallen/4||visit[i]||sample==stick[i])continue;
        if(nsum>totallen/4||visit[i])continue;
        visit[i]=true;
        if(nsum==totallen/4)//凑成一条边
        {
            if(DFS(0,number+1,1))//下一条边从第一根棒开始测试
            return true;
            //else
            //{
            //    sample=stick[i];//说明这根棒子不能在这种情况下被用
            //}
        }
        else
        {
            if(DFS(nsum,number,i+1))
            return true;
            //else
            //{
            //    sample=stick[i];
            //}
        }
        visit[i]=false;
    }
    return false;
    
}
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        
        cin>>m;
        totallen=0;
        for(int j=1;j<=m;j++)
        {
            cin>>stick[j];
            totallen+=stick[j];
        }
        memset(visit,false,sizeof(visit));
        sort(stick+1,stick+1+m,cmp);
        if(totallen%4!=0||stick[1]>totallen/4)
        {
            cout<<&quot;no&quot;<<endl;
        }
        else
        {
            if(DFS(0,0,1))//当前边的长度，拼好的边长数量，拼到第几个棒子
            cout<<&quot;yes&quot;<<endl;
            else 
            cout<<&quot;no&quot;<<endl;
            
        }
    }
}