Problem Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Input
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.
Output
For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
Sample Input
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
Sample Output
yes
no
yes
Source
University of Waterloo Local Contest 2002.09.21
#include<iostream>
#include<cstring>
using namespace std;
int m,edge;//木棍的个数,木棍的边长
int stick[];//木棍的长度
bool vis[];//是否用过木棍
bool flag;
void dfs(int n,int len,int i)//n是第几条边，len是这条边已有长度,i从第几条边开始查找（防止超时）
{
if(n==)//终止条件
{
flag=true;
return;
}
if(len==edge)
{
dfs(n+,,);
if(flag==true)
return ;
}
for(int j=i;j<=m;j++)
{
if(!vis[j])
{
if(stick[j]+len<=edge)
{
vis[j]=true;
dfs(n,len+stick[j],j+);
if(flag==true)
return ;
vis[j]=false;
}
}
} }
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>m;
edge=;
for(int i=;i<=m;i++)
{
cin>>stick[i];
edge+=stick[i];
}
if(edge%!=)//第一个剪枝：是否能组成正方形
{
printf("no\n");
continue;
}
edge/=;
int i;
for(i=;i<=m;i++)//第二个剪枝：木棍小于等于边长
{
if(stick[i]>edge)
break;
}
if(i!=m+)
{
printf("no\n");
continue;
}
memset(vis,false,sizeof(vis));
flag=false;
dfs(,,);
if(flag)
printf("yes\n");
else
printf("no\n");
}
return ;
}