poj1011 sticks

#include <iostream>
#include <algorithm>
using namespace std;

#define N 70

int stick[N], n;
bool used[N];

bool compare(const int &a, const int &b)
{
	return a > b;
}

/*
left                ，          ，
len          。
*/
bool Search(int left, int m, int len, int cur) 
{
	int i;
	
    if(left == 0){
		if(m == 2) return true;
		/*
		          ，                      ，
		               ，     false，         
		       ，           。
		*/
		for(cur = 0; used[cur]; cur++); 
		used[cur] = true;
		if( Search(len - stick[cur], m - 1, len, cur + 1) )
			return true;
		used[cur] = false; //  ，                
		return false; //     cur        ，    false
	}
	else {
		if(cur > n - 1) return false;
		/*
		  ：               ，          。
		*/
		for(i = cur; i < n; i++) 
		{
			if(used[i]) continue; //  ：       
			/*
			  ：
			               ，         ，
			                   
			*/
			if(stick[i-1] == stick[i] && !used[i-1]) 
				continue;
			//  ：                      
			if(stick[i] > left) 
				continue;
			used[i] = true;
			if( Search(left - stick[i], m, len, i + 1) )
				return true;
			used[i] = false; //  ，            
		}
	}
	return false;
}

int main()
{
	int i, sum;
    bool flag;
	
	while(scanf("%d", &n) && n)
	{
        for(sum = i = 0; i < n; i++)
		{
			scanf("%d", &stick[i]);
			sum += stick[i];
		}
		/*
		       ，            ，              。
		        。
		*/
        sort(stick, stick + n, compare);
		flag = false;
		for(i = stick[0]; i <= sum / 2; i++){ //       ，             
			if(sum % i == 0){ //             
				memset(used, false, sizeof(used));
				used[0] = true;
				if( Search(i - stick[0], sum / i, i, 1) ){
					flag = true;
					printf("%d
", i);
					break;
				}
			}
		}
		if(!flag) printf("%d
", sum);
	}
	return 0;
}