【DFS+剪枝】Square

https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/J
【题意】
给定n个木棍，问这些木棍能否围成一个正方形
【Accepted】
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 
 9 using namespace std;
10 int n;
11 const int maxn=22;
12 int a[maxn];
13 int sum=0;
14 bool vis[maxn];
15 int flag;
16 void DFS(int num,int len,int st)
17 {
18     if(flag) return;
19     if(num==4)
20     {
21         flag=1;
22         return;
23     }
24     if(len==sum)
25     {
26         DFS(num+1,0,0);
27         if(flag) return;
28     }
29     for(int i=st;i<n;i++)
30     {
31         if(!vis[i]&&len+a[i]<=sum)
32         {
33             vis[i]=true;
34             DFS(num,len+a[i],i+1);
35             if(flag)
36             {
37                 return;
38             }
39             vis[i]=false;
40         }
41     }
42 }
43 int main()
44 {
45     int T;
46     scanf("%d",&T);
47     while(T--)
48     {
49         memset(vis,false,sizeof(vis));
50         sum=0;
51         scanf("%d",&n);
52         for(int i=0;i<n;i++)
53         {
54             scanf("%d",&a[i]);
55             sum+=a[i];
56         }
57         if(sum%4!=0)
58         {
59             puts("no");
60             continue;
61         }
62         sum/=4;
63         flag=0;
64         for(int i=0;i<n;i++)
65         {
66             if(a[i]>sum)
67             {
68                 puts("no");
69                 flag=1;
70                 break;
71             }
72         }
73         if(flag==1) continue;
74         sort(a,a+n);
75         flag=0;
76         DFS(0,0,0);
77         if(flag==1)
78         {
79             puts("yes");
80         }
81         else
82         {
83             puts("no");
84         }    
85     }
86     return 0;
87 }
DFS+剪枝