poj 1011 Sticks

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define  inf 0x0f0f0f0f

using namespace std;

bool cmp(int x,int y)
{
    return x>y;
}

int a[65],n;
bool vis[65];

bool dfs(int nowlen,int Len,int x,int num)
{
    if (num==n) return true;
    int temp=0;
    for (int i=x;i<n;i++)
    {
        if (vis[i] || a[i]==temp) continue;
        vis[i]=true;
        if (nowlen+a[i]<Len)
        {
            if (dfs(nowlen+a[i],Len,i+1,num+1)) return true;
            else temp=a[i];
        }
        if (nowlen+a[i]==Len)
        {
            if (dfs(0,Len,0,num+1)) return true;
            else temp=a[i];
        }
        vis[i]=false;
        if (nowlen==0) break;
    }
    return false;
}

int main()
{
    int sum,maxx;
    bool flag;
    while (scanf("%d",&n)!=EOF && n)
    {
        memset(vis,0,sizeof(vis));
        sum=0;
        flag=false;
        for (int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sort(a,a+n,cmp);
        maxx=a[0];
        for (int i=maxx;i<=sum-i;i++)
        {
            if (sum%i==0 && dfs(0,i,0,0))
            {
                flag=true;
                printf("%d\n",i);
                break;
            }
        }
        if (!flag) printf("%d\n",sum);
    }
    return 0;
}