#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 70;

int w[N], sum, len, n, t;
bool st[N];

/*
1,优化搜索顺序
2,排除等效冗余
*/

//传入的参数:已经拼好的木棒数量cnt 正在拼的木棒长度cab  从哪一根木棍开始接idx
//dfs返回的值:当前使用的木棍是否可以拼在当前的木棒上
bool dfs(int cnt, int cab, int idx)
{
    //一定不会出现cnt==t的时候还有木棍没被使用过的情况
    if(cnt == t) return true;
    if(cab == len) return dfs(cnt+1,0,0);
    
    for(int i = idx; i < n ; i ++)
    {
        if(st[i]) continue;
        if(cab + w[i] > len) continue;
        
        st[i] = true;
        if(dfs(cnt, cab+w[i], i+1)) return true;
        st[i] = false;
        int j = i;
        while(j < n && w[i] == w[j]) j++;
        i = j - 1;

/*********************从这里开始就是第i根木棒拼接失败**************************/ 
        if(cab == 0 || cab + w[i] == len) return false;
    }
    return false;
}

int main()
{
    while(cin >> n && n)
    {
        sum = 0;
        memset(st, 0, sizeof st);
        
        for(int i = 0; i < n ; i ++)
        {
            scanf("%d", w+i);
            sum += w[i];
        }
        
        sort(w,w+n,greater<int>());
        len = w[0];
        //从max+min开始枚举len,且sum%len应该等于0
        //这个题应该有一些问题len从max+min开始枚举就是错误的,从max开始枚举是对的
        for(;len <= sum; len ++)
        {
            if(sum % len) continue;
            
            t = sum / len;

            if(dfs(0,0,0))
            {
                printf("%d\n", len);
                break;
            }
        }
    }
    return 0;
}

最后一个点TLE  280-290ms过不了,呜呜呜