DFS POJ 2362 Square

 1 /*
 2     DFS：问能否用小棍子组成一个正方形
 3     剪枝有3：长的不灵活，先考虑；若根本构不成正方形，直接no；若第一根比边长长，no
 4     这题是POJ_1011的精简版:)
 5 */
 6 #include <cstdio>
 7 #include <iostream>
 8 #include <cstring>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <algorithm>
13 using namespace std;
14 
15 const int MAXN = 22;
16 const int INF = 0x3f3f3f3f;
17 int a[MAXN];
18 bool vis[MAXN];
19 int len, sum;
20 int n, m;
21 
22 bool cmp(int x, int y)
23 {
24     return x > y;
25 }
26 
27 bool DFS(int ans, int cnt, int s)
28 {
29     if (cnt == 3)
30     {
31         return true;
32     }
33 
34     for (int i=s; i<=m; ++i)
35     {
36         if (!vis[i] && ans + a[i] <= len)
37         {
38             vis[i] = true;
39             if (ans + a[i] == len)
40             {
41                 if (DFS (0, cnt + 1, 1) == true)    return true;
42                 vis[i] = false;
43             }
44             else
45             {
46                 if (DFS (ans + a[i], cnt, i) == true)  return true;
47                 vis[i] = false;
48             }
49         }
50     }
51 
52     return false;
53 }
54 
55 int main(void)      //POJ 2362 Square
56 {
57     //freopen ("POJ_2362.in", "r", stdin);
58 
59     scanf ("%d", &n);
60     while (n--)
61     {
62         sum = 0;
63         memset (vis, 0, sizeof (vis));
64 
65         scanf ("%d", &m);
66         for (int i=1; i<=m; ++i)
67         {
68             scanf ("%d", &a[i]);
69             sum += a[i];
70         }
71         sort (a+1, a+1+m, cmp);     //Cut 1
72 
73         if (m < 4 || sum % 4 != 0)      //Cut 2
74         {
75             puts ("no");    continue;
76         }
77         len = sum / 4;
78 
79         if (a[1] > len)     //Cut 3
80         {
81             puts ("no");        continue;
82         }
83 
84         if (DFS (0, 0, 1) == true) puts ("yes");
85         else    puts ("no");
86     }
87 
88     return 0;
89 }
90 
91 
92 /*
93 yes
94 no
95 yes
96 */