> 
> #include <iostream>
> #define MAX 100
> using namespace std;
> 
> int stick[MAX];
> int used[MAX];
> int n, nLen;
> int sumL, num;
> int yes;
> 
> int cmp(const void *r1, const void *r2)
> {
> 	return *(int *)r2 - *(int *)r1;
> }
> 
> 
> 
> int dfs(int nl, int ni, int tn)//nl:now len;tn:now num;ni:search tx;
> {
> 	int i;
> 	if(yes)return 1;
> 	if(tn == num){yes = 1; return 1;}        
> 	for(i=ni; i<n; i++)
> 	{
> 		if(!used[i])
> 		{
> 			if(nl+stick[i]<nLen)
> 			{
> 				now=stick[i];
> 				used[i]=1;
> 				if(dfs(nl+stick[i], i+1, tn))return 1;
> 				if(tn == num){yes = 1; return 1;}
> 				if(yes)return 1;
> 				used[i]=0;//??
> 				break;
> 			}
> 			else if(nl+stick[i]==nLen)
> 			{
> 				used[i]=1;
> 				if(dfs(0, 0, tn+1))return 1;
> 				if(tn == num){yes = 1; return 1;}
> 				if(yes)return 1;
> 				used[i]=0;
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> 
> int main()
> {
> 	int i;
> 	while(scanf("%d", &n) && n)
> 	{
> 		sumL = 0;
> 		memset(stick, 0, sizeof(stick));
> 		//Input
> 		for(i=0; i<n; i++)
> 		{
> 			scanf("%d", &stick[i]);
> 			sumL += stick[i];
> 		}
> 		//Sort from big to small
> 		qsort(stick, n, sizeof(int), cmp);
>  		for(i=stick[0]; i<sumL; i++)
> 		{
> 			yes = 0;
> 			if(sumL%i == 0)
> 			{
> 				memset(used, 0, sizeof(used));
> 				num = sumL/i;
> 				nLen = i;
> 				dfs(0, 0, 0);
> 				if(yes == 1)break;
> 			}
> 		}
> 		printf("%d\n", nLen);
> 	}
> 	return 0;
> }
> 
>