在woj都能过。。。

#include <iostream>
#include <stdio.h>
//#include <string>
#include <algorithm>
//#include <stdio.h>   
//#include <stdlib.h>
//#include <cmath>

using namespace std;

int n,a[100],f[100];
bool cmp(const int &x,const int &y)
{
     return x>y;
}

bool dfs(int m,int t,int s)
{
     //cout<<m<<" "<<t<<" "<<s<<endl;
     if (t==0) return dfs(m-1,s,s);
     if (m==0) return true;
     int k=0;
     while (k<n && f[k]) k++;
     if (k==n) return false;
     if (t==s)
     {
              
              f[k]=1;
              return dfs(m,t-a[k],s);
     }
     int h=-1;
     for (int i=k;i<n;i++)
     if (!f[i] && t>=a[i] && a[i]!=h)
     {
               f[i]=1;
               if (dfs(m,t-a[i],s)) return true;
               f[i]=0;
               h=a[i];
     }
     return false;
     
}

int main()
{
    //freopen("aaain.txt","r",stdin);
    //freopen("aaaout.txt","w",stdout);
    int s,max;
    bool pp;
    while (scanf("%d",&n)==1)
    {
          if (n==0) break;
          s=0;max=0;
          for (int i=0;i<n;i++)
          {
                   scanf("%d",&a[i]);
                   s+=a[i];
                   if (max<a[i]) max=a[i];
          }
          sort(a,a+n,cmp);
          
          pp=true;
          for (int i=max;i<=s/2;i++)
          if (s%i==0)
          {
              for (int k=0;k<100;k++) f[k]=0;      
              if (dfs(s/i,i,i))
              {
                         pp=false;
                         printf("%d\n",i);
                         break;
              }
              
          }
          if (pp) printf("%d\n",s);
    }
          
    
    return 0;
}