#include<bits/stdc++.h> #define ll long long using namespace std; ll read() { ll r=0,f=1;char c=getchar(); while((c<'0'||c>'9')&&(c!='-')) c=getchar(); if(c=='-') f=-1,c=getchar(); while(c>='0'&&c<='9') r=r10+c-'0',c=getchar(); return rf; } ll a[101],v[101],n,len,cnt; bool dfs(ll stick,ll cab,ll last) { if(stick>cnt) return true; if(cablen) return dfs(stick+1,0,1); ll failess=0; for(int i=last;i<=n;i++) if(!v[i]&&cab+a[i]<=len&&failess!=a[i]) { v[i]=1; if(dfs(stick,cab+a[i],i+1)) return true; failess=a[i]; v[i]=0; if(cab0||cab+a[i]==len) return false; } return false; } ll cmp(ll a,ll b) { return a>b; } int main() { // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); n=read(); ll sum=0,val=0; for(int i=1;i<=n;i++) { ll b=read(); if(b>50) continue; a[i]=b; sum+=a[i]; val=max(val,a[i]); } sort(a+1,a+n+1,cmp); for(len=val;len<=sum;len++) { if(sum%len) continue; cnt=sum/len; memset(v,0,sizeof(v)); if(dfs(1,0,1)) break; } cout<<len<<endl; return 0; }

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
int a[100],book[100];
bool cmp(int x,int y)
{
    return x>y;
}
int len,cnt;
int dfs(int num,int lasti,int l)
{
    //num为拼好的个数，lasti为上一个的编号，l为已拼成的长度
    if(num==cnt+1) //表示拼成了cnt根小木棍且小木棍没有剩余，符合题目所求
        return 1;
    if(l==len)//拼成一个len长度num+1
        return dfs(num+1,1,0);
    for(int i=lasti; i<=n; i++)//剪枝，当用木棍i拼接最初的木棍时，可以从第i+1后的木棍开始搜索，因为排序，前面的木棍已经用过了
    {
        if(!book[i]&&l+a[i]<=len)  //保证当前长度加上正在选的小木棍长度不大于len，如果大于len就是没有小木棍可以拼成len长度的小木棍，不符合条件
        {
            book[i]=1;
            if(dfs(num,i+1,l+a[i]))
                return 1;
            book[i]=0;//深搜搜索后要取消标记
            if(l==0||l+a[i]==len)//剪枝，找不到能拼成len长度的木棍
                return 0;
            while(a[i]==a[i+1])//去重剪枝 相同长度的不符合条件的则不需再搜索
                i++;
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    int s=0;
    //排序，最初小木棍的长度一定大于等于砍断后的小木棍的最大的长度，并且小于所有小木棍的长度之和
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        s+=a[i];
    }
    sort(a+1,a+1+n,cmp);
    //所有小木棍的长度之和为s，则拼成若干根的小木棍的长度一定能被s整除，否则就拼不成，因为拼成的小木棍必须是整数根
    for(len=a[1]; len<=s; len++)
    {
        if(s%len==0)
        {
            cnt=s/len;
            if(dfs(1,1,0))
                break;
        }
    }
    printf("%d\n",len);
    return 0;
}