详细请查看注释

参考代码：

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

using namespace std;

const int N = 70;

int n, sum, length, w[N], vis[N];

/*
    剪枝优化：
        1. 大木棍长度一定是可以整除总和的
        2. 优化搜索顺序，从大到小枚举
        3. 排序等效冗余
            1. 按照组合数枚举
            2. 若当前长度小木棍失败，则直接跳过与当前长度相等的木棍
            3. 大木棍第一个位置失败或最后一个位置失败则一定失败

        证明一下第三条第三点：
            第一个位置失败则一定失败：假设该小木棍放到当前开头失败，放在后续其他大木棍成功!
                则我们可以在该大木棍中交换位置，将其交换到第一个位置，然后我们可以将该大木棍与失败的大木
                棍交换，会发现将该小木棍放到开始可以得到合法解，与假设矛盾！则表示第一个位置失败，则一定失败！
            最后一个位置失败则一定失败：假设该小木棒放到当前结尾失败，放在后续大木棍成功!
                由于当前位置没有放失败的小木棍，则一定由其他多根小木棒拼接而成，我们将失败的小木棍放到后续
                大木棍可以成功。会发现原来的位置和当前放到后续位置的失败木棍长度的一致的，因此我们可以直接
                交换失败小木棍到原大木棍合拼的位置，与假设矛盾！则表示结尾失败，一定失败！
*/

// 当前大木棍个数 当前大木棍长度 上次枚举到的小木棍编号的下一个位置
// 剪枝优化三：排除等效冗余，使用组合数枚举
bool dfs(int u, int len, int start){
    if(u * length == sum) return true;
    // 当前大木棍已完整拼接，使用新木棍
    if(len == length) return dfs(u + 1, 0, 0);

    for(int i = start; i < n; i ++){
        if(!vis[i] && len + w[i] <= length){
            vis[i] = true;
            if(dfs(u, len + w[i], i + 1)) return true;
            vis[i] = false;

            // 能走到这里表示上面是失败的！
            // 剪枝优化四：排除等效冗余
            // 1. 大木棍第一个位置失败或最后一个位置失败则一定失败
            if(!len || len + w[i] == length) return false;
            // 2. 若当前小木棍失败，则跳过与当前长度一致的小木棍
            int j = i;
            while(j < n && w[j] == w[i]) j ++;
            i = j - 1;
        }
    }
    return false;
}

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

        // 剪枝优化一：优化搜索顺序，从大到小搜
        sort(w, w + n, greater<int>());

        memset(vis, false, sizeof vis);
        length = 1;
        while(true){
            // 剪枝优化二：可行性剪枝，木棍长度一定是总和的约数
            if(sum % length == 0 && dfs(0, 0, 0)){
                cout << length << endl;
                break;
            }
            length ++;
        }
    }
    return 0;
}