> #include<iostream.h>
> #include<stdlib.h>
> int *stick,*isused,n;
> int Connect(int leftstick,int leftlen,int len);
> int compare(const void* a,const void* b);
> void main()
> {
> 	int i,j,len,sum;
> 	while(cin>>n)
> 	{
> 		if(n == 0) break;
> 		sum = 0;
> 		stick = new int[n] ; isused = new int[n];
> 		for(i = 0 ; i < n ; i++)
> 		{
> 			cin>>stick[i]; sum += stick[i]; isused[i] = 0;
> 		}
> 		qsort(stick,n,sizeof(int),compare);
> 		for(len = stick[0] ; len <= sum ; len++)
> 		{
> 			if(sum % len == 0)
> 			{
> 				if(Connect(sum,len,len)) { cout<<len<<endl; break;}		
> 				for(j = 0 ; j < n ; j++) isused[j] = 0 ;
> 			}
> 		}
> 		delete []stick; delete []isused;
> 	}
> }
> int compare(const void* a,const void* b)
> {
> 	return *(int*)b - *(int*)a ;
> }
> int Connect(int leftstick,int leftlen,int len)
> {
> 	if(leftstick == 0 && leftlen == 0) return 1;
> 	if(leftlen == 0) leftlen = len;
> 	int j;
> 	for(j = 0 ; j < n ; j++)
> 	{
> 		if(isused[j] == 0 && stick[j] <= leftlen)
> 		{
> 			isused[j] = 1; 
> 			if(Connect(leftstick-stick[j],leftlen-stick[j],len)) return 1;
> 			isused[j] = 0 ;	
> 		}
> 	}
> 	return 0;
> }