题目：
Square
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15102 Accepted Submission(s): 4751
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
解题心得：
1、一开始在看到这道题的时候真的很蒙蔽，不知道怎么递归，怎么判断是否可以拼成正方形，其实这道题只要利用正方形的性质就可以了，正方形有四条边并且四条边一样长，所以在递归的时候只需要递归拼成的边的长度和边的个数就行了，但是按照这种普通的思路会超时，这就很尴尬了，然后就剪枝呗。
2、这个题的剪枝比较复杂，给出的n小于4的直接剪去，给出的所有的和不是4的倍数的直接减去，最大的数超过了边长的直接减去，看似减得差不多了但是还是会超时，这里有一个小的技巧，在递归边长的时候是将几个数相加得到的边长，这个时候就可以先排一个序然后从小到大开始加，每一次递归的元素再加加在边长上排序好的那个数的位置就行了。
#include<bits/stdc++.h>
using namespace std;
int a[25];
bool flag,vis[25];
int n,ave;
void dfs(int num,int len,int pos)//需要递归的元素以此是：边的条数，边的长度，加上的数的位置
{
if(num == 3 || flag)//由于之前预处理了，直接得到三条边就好，第四条边自动就出来了
{
flag = true;
return ;
}
if(len == ave)
{
dfs(num+1,0,0);
return;
}
for(int i=pos;i<n;i++)
{
if(!vis[i] && (len + a[i] <= ave))
{
vis[i] = true;
dfs(num,len+a[i],i+1);
vis[i] = false;
}
}
}
int main()
{
int t;
int Max = -1;
int sum;
scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
flag = false;
sum = 0;
Max = -1;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum += a[i];
}
sort(a,a+n);
if(n <= 3)//正方形有四条边
{
printf("no
");
continue;
}
ave = sum /4;//平均每一条边的边长
if(sum % 4)//不是4的倍数的直接减去
{
printf("no
");
continue;
}
if(a[n-1] > ave)//最大的一个数比平均边长还大的直接减去
{
printf("no
");
continue;
}
dfs(0,0,0);
if(flag)
printf("yes
");
else
printf("no
");
}
}
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,cnt,sum;
struct node
{
int lenth;
int mark;
}stick[25];
int cmp(node a,node b)
{
return a.lenth>b.lenth;
}
int dfs(int len,int count,int l,int pos)
{
if(count==4)return 1;
for(int i=pos;i<n;i++)
{
if(stick[i].mark)continue;
if(len==(stick[i].lenth+l))
{
stick[i].mark=1;
if(dfs(len,count+1,0,0))
return 1;
stick[i].mark=0;
return 0;
}
else if(len>(stick[i].lenth+l))
{
stick[i].mark=1;
l+=stick[i].lenth;
if(dfs(len,count,l,i+1))
return 1;
l-=stick[i].lenth;
stick[i].mark=0;
if(l==0) return 0;
while(stick[i].lenth==stick[i+1].lenth)i++;
}
}
return 0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d",&n);
cnt=sum=0;
for(int i=0;i<n;i++)
{
scanf("%d",&stick[i].lenth);
sum+=stick[i].lenth;
stick[i].mark=0;
}
sort(stick,stick+n,cmp);
if(sum%4||n<4)
{
cout<<"no"<<endl;
continue;
}
cnt=sum/4;
if(dfs(cnt,0,0,0))
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
return 0;
}