poj1011木棒

老实说，我做这道题时关于那些剪枝都是看了师兄的博客然后慢慢研究每一条语句，才发现意义深厚，很多都是我想不到但又实际可行的剪枝让我佩服不已~~，不过我这道能在poj上过是因为它的测试数据很水，而下面一组用例就不只用了1s了~~~

/*
9
5 2 1 5 2 1 5 2 1


4
1 2 3 4


12
1 1 2 2 2 3 3 3 3 3 3 4


27
15 3 2 4 11 1 8 8 8 15 3 2 4 11 1 8 8 8 15 3 2 4 11 1 8 8 8


9
15 4 3 1 2 8 11 8 8


45
15 3 2 11 4 1 8 8 8 15 3 2 11 4 1 8 8 8 15 3 2 11 4 1 8 8 8 15 3 2 11 4 1 8 8 8
15 3 2 11 4 1 8 8 8


64
40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40
40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40
40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40 40
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int flag[66],num;
int cmp(const void* a,const void* b)
{
	return (*(int *)b-*(int *)a);
}
int work(int a[],int n,int sum,int news,int number,int ss)
{
	int i,same;
	same=-1;
	if(number==n)
		return 1;
	
	for(i=ss;i<n;i++)
	{
		if(flag[i]!=0)
			continue;
		
			flag[i]=1;
			if(news+a[i]<sum)
			{
				if(a[i]!=same)
					if(work(a,n,sum,news+a[i],number+1,i))
						return 1;
					else
					{
						same=a[i];
					}
			}
			if(news+a[i]==sum)
			{
				if(a[i]!=same)//我做这道题时，一直忘记加这个条件，（超时！！！）害得我想了一天~~~~~，上面相同的条件又记得，我cao！！
				if(work(a,n,sum,0,number+1,0))
						return 1;
					else
					{
						same=a[i];
					}
			}


			flag[i]=0;
		
		if(news==0)//还有这个剪枝很重要，当全都没选过时，你选第一根棒都不能匹配，下面就不用递归了，直接false！！
			break;
	}


	return 0;
}


int main()
{
	int n;
	int i,a[66];
	while(scanf("%d",&n)&&n)
	{
		num=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			num+=a[i];
		}
		qsort(a,n,sizeof(a[0]),cmp);
		for(i=a[0];i<=num;i++)
		{
			memset(flag,0,sizeof(flag));
			if(num%i==0 && work(a,n,i,0,0,0))
			{
				printf("%d\n",i);
				break;
			}
		}
		
		
	}
	return 0;
}