//yxc的代码详细加注释，方便大家理解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=64;

int sticks[N];
bool st[N];
int n,sum,length;

bool dfs(int u,int cur,int start)   //排到第u个木棍，该木棍长度为cur，从start开始枚举
{
    if(u*length==sum)return true;   //DFS完成

    if(cur==length)return dfs(u+1,0,0);//该木棍已经用完
    for(int i=start;i<n;i++)        //枚举多种情况
    {
        if(st[i])continue;          //已经被访问过了
        int l=sticks[i];            //保存第i根木棍的长度
        if(l+cur>length)continue;   //如果加上后超出木棍长度
        st[i]=1;                    //标记为已用
        if(dfs(u,cur+l,i+1))return true;//DFS成功
        st[i]=0;                    //复原现场

        if(!cur)return false;       //所有木棒中最大的木棒(第一个木棒)放入失败，就一定失败
        if(cur+l==length)return false;//最后一根木棒放入后可以达到length却没有成功，就一定失败

        int j=i;                    //跳过相同部分
        while(j<n&&sticks[j]==l)j++;//跳过相同部分
        i=j-1;                      //因为这次循环后i要加一，所以先减一
    }
    return false;                   //失败
}

int main()
{
    while(cin>>n,n)
    {
        sum=length=0;               //清空
        for(int i=0;i<n;i++)        //读入
        {
            int l;
            cin>>l;
            sticks[i]=l;
            sum+=l;                 //统计长度
            length=max(length,l);   //统计最大长度
        }
        sort(sticks,sticks+n);      //从小到大排序
        reverse(sticks,sticks+n);   //反过来，就是从大到小排序，从大的开始暴搜，方案数相对减少
        memset(st,0,sizeof st);     //清空
        while(true)
        {
            if(sum%length==0&&dfs(0,0,0))//如果k*length=sum,说明长度可以为length
            {
                cout<<length<<endl;
                break;
            }
            length++;               //枚举下一个长度
        }
    }
    return 0;
}

挑战模式:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=70;

bool st[N];

int n;
int sticks[N];
int length,sum;

bool DFS(int u,int cur,int start)
{
    if(u*length==sum)return true;
    if(cur==length)return DFS(u+1,0,1);

    for(int i=start;i<=n;i++)
    {
        if(st[i])continue;
        int l=sticks[i];
        if(cur+l>length)continue;
        st[i]=1;
        if(DFS(u,cur+l,i+1))return true;
        st[i]=0;

        if(!cur)return false;
        if(cur+l==length)return false;

        int j=i;
        while(sticks[j]==sticks[i])j++;
        i=j-1;
    }
    return false;
}

int main()
{
    while(true)
    {
        scanf("%d",&n);
        length=sum=0;
        if(!n)return 0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&sticks[i]);
            length=max(length,sticks[i]);
            sum+=sticks[i];
        }
        memset(st,0,sizeof st);
        sort(sticks+1,sticks+n+1,[](const int &a,const int &b){return a>b;});
        while(length<=sum)
        {
            if(sum%length==0&&DFS(1,0,1))
            {
                printf("%d\n",length);
                break;
            }
            length++;
        }
    }
    return 0;
}