Square

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13562    Accepted Submission(s): 4298

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 


思路：
题意，给出这么多棍棍，问你能不能拼成正方形。想法肯定是DFS，但是如果是朴素的DFS的话，TLE。。所以这里又需要用剪枝的思想。。。
这里需要剪枝的几个地方是：
1、进行DFS搜索，要标记已经使用了的棍子，一旦不符合要求，就要回溯，并且棍子成为没有使用的状态。
2、当符合要求的棍子数等于5时，说明已经全部构成正方形的边长，结束。
3、每当边长达到要求是，进入下一根棍子DFS搜索。
4、还有最重要的一点：每次遍历一边棍子不要从0开始，从上一次搜索状态的下一根棍子开始遍历，否者会超时。
5、当flag为true，return的不仅是使flag变为true的那一次dfs，而且还要return 整个dfs，即结束全部的寻找。我就是在这里T了好长时间。。。

代码： 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int s[25];
int book[25];
int sum;
int bianchang;
int n;
bool flag=false;
//第一次TLE了，dfs部分需剪枝 
void dfs(int num,int nowlen,int dth)
{
	if(num>4)
	{
		flag=true;
		return ;
	}
	
	if(dth>n)
	{
		return ;
	}
	
	if(nowlen==bianchang)
    {
        dfs(num+1,0,0);
        if(flag==true)return;//剪枝处1 
    }
    
    for(int i=dth;i<n;i++)
    {
    	if(book[i]==0&&s[i]+nowlen<=bianchang) 
        {
            book[i]=1;
            dfs(num,s[i]+nowlen,i+1);
            if(flag==true)return ;//剪枝处2 
            book[i]=0; 
        }
        else if(book[i]==0&&s[i]+nowlen>bianchang) return;
    }
} 

int main()
{
	freopen("in.txt","r",stdin);
	int num;
	cin>>num;
	while(num--)
	{
		int sum=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%d",&s[i]);
			sum+=s[i];
		}
		if(sum%4!=0)
		{
			cout<<"no"<<endl;
			continue;
		} 
		else bianchang=sum/4;
		bool flagg=true;
		for(int i=0;i<n;i++)
		{
			if(s[i]>bianchang)
			{
				flagg=false;
				break;
			}
		}
		if(flagg==false)
		{
			cout<<"no"<<endl;
			continue;
		}
		memset(book,0,sizeof(book));
		sort(s,s+n);
		flag=false; //每次记得再将flag初始化 
		dfs(1,0,0);
		if(flag==true)cout<<"yes"<<endl;
		else cout<<"no"<<endl;	
	}
	return 0;
}