C++ 代码

/*

枚举顺序：从大到小枚举木棒的长度，再依次从前往后拼接每一根木棒，如果所有木棍可以被用完，说明合法。

一、可行性剪枝：木棒的长度一定要是总长度的约数
二、优化搜索顺序剪枝：从大到小枚举木棍
三、排除等效冗余：
①枚举组合数而不是排列数（传一个参数start，表示开始的位置）

②在拼接一根木棒时，如果某根木棍失败了，那么与它长度相同的木根同样会失败，应该直接跳过
证明：假设当前方案合法，且在拼接A木棒时，x木棍失败了，但是与它等长的y木棍成功了。
      因为方案是合法的，所以x木棍会在接下来的B木棒中拼接成功，此时将x木棍和y木棍交换，结果仍然成立，
      说明将x木棍放在A木棒中拼接成功，这与假设矛盾。说明假设不成立。

③在拼接一根木棒时，如果某根木棍作为第一根而失败，那么这个方案直接失败。
证明：假设木棍x作为木棒A的第一根木棍拼接失败了，但是方案仍然成功了。
      因为方案成功了，说明木棍x会在接下来的某一木棒B中拼接成功，
      因为在拼接木棒A时，木棍x是现有的未使用的木棍中最长的
     (因为如果要重新拼接一根木棒，那么会从头开始遍历所有木棍，直到找到未使用过的木棍，所以当然最长)
      所以，如果木棍x在木棒B中拼接成功，说明木棍x肯定在木棒的最开始，
      再将木棒A、B交换，说明木棒A存在一种以木棍x开头的方案，与假设矛盾。

④在拼接木棒A时，如果木棍x作为最后一根拼接且木棒A拼接成功，但是接下来的木棒在拼接时却会失败，那么这个方案不成立。
证明：假设在拼接木棒A时，如果木棍x作为最后一根拼接且木棒A拼接成功，但是接下来的木棒在拼接时却会失败，方案仍然成立，
      那么木棒A的最后一段将会由其他木棍y、z来拼接，同时木棍x会转移到其他木棒中，此时将木棍y、z和木棍x交换，结果仍然成立，
      说明木棍x作为木棒A最后一段拼接时可以成功，并且之后的木棍都成功，这与假设“接下来的木棒在拼接时却会失败”矛盾。
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;

int w[N];
int n;
int length;
int sum;
bool st[N];

bool cmp(int a, int b)
{
    return a > b;
}

bool dfs(int u , int cur , int start)//第u根木棒(从0开始计数)、当前木棒长度、起始木棍下标
{
    if(u * length == sum) return true;
    if(cur == length) return dfs(u + 1 , 0 , 0);

    //剪枝3-1 从start开始枚举
    for(int i = start ; i < n ; i++)
    {
        if(st[i] || cur + w[i] >  length) continue;

        st[i] = true;
        if(dfs(u , cur + w[i] , i + 1)) return true;;
        st[i] = false;


        //3-3剪枝 cur==0，说明当前拼接的是木棒的第一根木棍，又因为失败了说明是第一根木棍失败了
        if(!cur) return false;

        //3-4剪枝 cur + w[i] == length，说明当前木棍恰好凑满，但是在后面的木棒拼凑时失败了
        if(cur + w[i] == length) return false;

        //3-2剪枝
        int j = i;
        while(j < n && w[j] == w[i]) j++;
        i = j - 1;
    }
    return false;
}

int main()
{
    while(cin >> n , n)
    {
        memset(st , 0 , sizeof st);

        sum = 0;
        for(int i = 0 ; i < n ; i++)    cin >> w[i] , sum += w[i];

        sort(w , w + n , cmp);

        length = 1;
        while(true)
        {
            if(sum % length == 0 && dfs(0 , 0 , 0))
            {
                cout << length << endl;
                break;
            }
            length++;
        }

    }
    return 0;
}