木棒

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

const int N=70;

int n;
int w[N];
int sum;
bool st[N];
int len;
//dfs 蹦着跳着选择哪一根木棍的写法
//用st[]数组，传一个start
bool dfs(int u,int s,int start)
{
    if(u*len==sum) return true;
    if(s==len) return dfs(u+1,0,0);
    
    for(int i=start;i<n;i++)
    {
        if(st[i]) continue;//被遍历过
        if(s+w[i]>len) continue;
        
        st[i]=true;
        if(dfs(u,s+w[i],start+1)) return true;
        st[i]=false;
        if(!s) return false;//在当前大棍放的第一个木棍失败
        if(s+w[i]==len) return false;//如果+w[i]后==len，表示这根木棒的拼接是成功的，但仍然返回了false,就证明后面的木棍没有匹配成功，所以这个方案错误
        int j=i;//失败，则把与失败那根长度相同的木棍都略过
        while(j<n&&w[j]==w[i]) j++;
        i=j-1;
    }
    
    return false;
}
int main()
{
    while(cin>>n,n)
    {
        sum=0;
        memset(st,0,sizeof st);
        for(int i=0;i<n;i++)
        {
            cin>>w[i];
            sum+=w[i];
        }
        sort(w,w+n);
        reverse(w,w+n);
        len=1;
        while(true)
        {
            if(sum%len==0&&dfs(0,0,0))
            {
                printf("%d\n",len);
                break;
            }
            len++;
        }
    }
    return 0;
}