木棍
根据别人的代码改写的，大体思路没变，主要是剪枝的思想。

//用scanf防止超时
//剪枝 + dfs 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool cmp(int a, int b){
	return a>b;
}
int sticks[70], used[70];
int length,cntt;
int n;
//dep 已经拼接好的木棍数
//conLen 已经拼好的长度
//pos 当前的位置 
bool dfs(int dep, int conLen, int pos){
	if(dep == cntt) return true; //木棍数量一致 直接返回 暗含总长一致 
	if(conLen == length) return dfs(dep+1,0,0); //拼好一根后 继续拼另一根 
	for(int i=pos;i<n;i++){ //从大到小顺序搜索 
		if(!used[i] && conLen+sticks[i]<= length){
			used[i]=1;
			if(dfs(dep, conLen+sticks[i], i+1)) return true;
			used[i]=0;
			if(conLen==0) return false; //剪枝1 第一根
			while(i+1<n &&sticks[i+1]==sticks[i]) i++; //剪枝2 相同长度 
		}
	}
	return false;//都不满足 返回false 
}  
int main(){	
	while(scanf("%d",&n)!=EOF&&n!=0){	
		int sum=0;
		for(int i=0;i<n;i++){
			scanf("%d",sticks+i);
			sum+=sticks[i];
		}
		sort(sticks,sticks+n,cmp);
		for(int j=sticks[0];j<=sum;j++){
			if(sum%j!=0) continue;
			memset(used,0,sizeof(used));
			length=j;
			cntt=sum/j;
			if(dfs(0,0,0)) {
				printf("%d\n",j);
				break;
			}
		}
	}
	return 0;
}