【DFS+剪枝】Square

https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/J

【题意】

给定n个木棍，问这些木棍能否围成一个正方形

【Accepted】

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 using namespace std;

 int n;

 const int maxn=;

 int a[maxn];

 int sum=;

 bool vis[maxn];

 int flag;

 void DFS(int num,int len,int st)

 {

     if(flag) return;

     if(num==)

     {

         flag=;

         return;

     }

     if(len==sum)

     {

         DFS(num+,,);

         if(flag) return;

     }

     for(int i=st;i<n;i++)

     {

         if(!vis[i]&&len+a[i]<=sum)

         {

             vis[i]=true;

             DFS(num,len+a[i],i+);

             if(flag)

             {

                 return;

             }

             vis[i]=false;

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         memset(vis,false,sizeof(vis));

         sum=;

         scanf("%d",&n);

         for(int i=;i<n;i++)

         {

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

             sum+=a[i];

         }

         if(sum%!=)

         {

             puts("no");

             continue;

         }

         sum/=;

         flag=;

         for(int i=;i<n;i++)

         {

             if(a[i]>sum)

             {

                 puts("no");

                 flag=;

                 break;

             }

         }

         if(flag==) continue;

         sort(a,a+n);

         flag=;

         DFS(,,);

         if(flag==)

         {

             puts("yes");

         }

         else

         {

             puts("no");

         }

     }

     return ;

 }

DFS+剪枝