TLEon#30

#include<bits/stdc++.h>
using namespace std;
int n,sum,k;
int a[70],f[70];
bool dfs(int x,int lst,int sum_){
    if(x*k==sum)return true;
    if (sum_==k)return dfs(x+1,0,0);
    int last=0;
    for (int i=lst;i<n;++i){
        if (!f[i] && sum_+a[i]<=k && a[i]!=last){
            f[i]=1;
            if(dfs(x,i+1,sum_+a[i]))return true;
            f[i]=0;
            last=a[i];
            if(sum_==0||sum_+a[i]==k)break;
            if(sum_+a[i]==k&&!dfs(x,i+1,sum_+a[i])) 
                return false;
        }
    }
    return false;
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
        sum+=a[i];
    }
    sort(a,a+n,greater<int>());
    for(k=a[0];k<=sum;++k){
        if(sum%k!=0)continue;
        if(dfs(1,0,0)){
            printf("%d",k);
            break;
        }
    }
    return 0;
}