Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

3

4 1 1 1 1

5 10 20 30 40 50

8 1 7 2 6 4 4 3 5

yes

no

yes

University of Waterloo Local Contest 2002.09.21

 #include <stdio.h>

 #include<string.h>

 int a[];

 int vist[];

 int sum;

 int l;

 int n;

 int flag;

 void Dfs(int t, int len, int index)

 {

     if (t == )

     {

         flag = ;

         return ;

     }

     if (len == l)

     {

         Dfs(t + , , );

         if (flag)//优化时间

         {

             return ;

         }

     }

     for (int i = index; i < n; i++)//从index开始优化时间

     {

         if (vist[i]== && a[i] + len <= l)

         {

             vist[i] = ;

             Dfs(t, a[i] + len, i + );

             if (flag)//优化时间

             {

                 return;

             }

             vist[i] = ;

         }

     }

 }

 int main()

 {

     int i,t;

     scanf("%d", &t);

     while (t--)

     {

         sum = ;

         scanf("%d", &n);

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

         {

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

             sum += a[i];

         }

         if (sum %  != )//简答的优化

         {

             puts("no");

             continue;

         }

         l = sum / ;

         for (i = ; i < n; i++)//有比边长大的边就不行

         {

             if (a[i] > l)

             {

                 break;

             }

         }

         if (i != n)

         {

             puts("no");

             continue;

         }

        memset(vist, , sizeof(vist));

         flag = ;

         Dfs(, , );

         if (flag)

         {

             puts("yes");

         }

         else

         {

             puts("no");

         }

     }

     return ;

 }