枚举每根木棍的长度，使用DFS组合每根木棍，检查此长度是否能组合出方案。

对于DFS，状态为：

1. 当前组合第x根木棍
2. 当前木棍已组合出now长度
3. 上一根组合的零件为front

剪枝方案：

1. 从大到小枚举 （优化搜索顺序）
2. 每次组合时，只组合比上一个零件小的零件。有顺叙的组合木棍（排除等效冗余）
3. 对于组合某个木棍的第一个零件，如果没有方案使得第一个零件可以组合出完整的木棍，说明该零件也无法在后续枚举中使用，故直接排除此方案（排除等效冗余）
4. 如果当前零件刚好可以组合完整的木棍，且此方案无效，说明无论后续如何组合此空余位置，后续零件也无法组合出有效木棍，故直接排除此方案（排除等效冗余）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N = 100;
int line[N], n, sum, mx, cnt, len;
bool vis[N];
 
bool DFS(int x, int now, int front) {
	if(x > cnt)return true;
	if(now == len)return DFS(x+1, 0, 0);
	int last = 0;
	for(int i = front + 1; i <= n; i++) {
		if(vis[i] || now + line[i] > len || line[i] == last) continue;
		vis[i] = true;
		if(DFS(x, now + line[i], i)) return true;
		vis[i] = false;
		last = line[i];
		if(now == 0 || now + line[i] == len)return false;
	}
	return false;
}
 
bool cmp(int a, int b) {
	return a > b;
}
 
int main() {
	while(scanf("%d", &n) && n) {
		sum = 0, mx = 0;
		memset(vis, false, sizeof(vis));
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &line[i]);
			sum += line[i]; mx = max(line[i], mx);
		}
		sort(line+1, line+1+n, cmp);
		for (len = mx; len <= sum; ++len) {
			if(sum % len) continue;
			cnt = sum / len;
			if(DFS(1, 0, 0)) {
				printf("%d\n", len);
				break;
			}
		}
	}
	return 0;
}