分析

• 首先明确一下概念：木棒指原来为被砍断的，木棍指砍断后的。

• 我们从小到大依次枚举每一根木棒的长度length，然后依次枚举每个木棒是由哪些木棍拼出来的。

• 考虑如何剪枝：

（1）优化搜索顺序：我们应该先枚举比较长的木棍，这样分支比较少。

（2）排除等效冗余：

​ （2.1）如果一个木棒可以由三个木棍拼接而成，那么这三个木棍的顺序无所谓，因此我们应该按照组合数的顺序来枚举，具体实现可以通过在递归函数中传入一个start参数，即下一根木棍的下标要从哪里开始。

​ （2.2）如果当前木棍加到当前木棒中失败了，则直接略过后面所有长度相等的木棍。

可以用反证法证明。比如3，4号木棍长度相同，3号木棍不能放入当前木棒中（即不是一个合法方案），而4号木棍却可以放入（即是一个合法方案），那么3号木棍一定会被放入到后面的某个木棒中，此时组成一个合法方案，我们可以交换3，4的位置，此时仍然是一个合法方案，矛盾。

​ （2.3）如果是木棒的第一根木棍失败，则一定失败。

可以用反证法证明。由于在拼木棒时从大到小选择每根木棍，所以如果当前木棍放在后面某根木棒中合法了，那么如果是放在了第一根，那么可以将两个长木棍交换，此时也一定是合法解，矛盾；如果不是放在了第一根，那么当前木棒的第一根一定是当前木棍之前的某根木棍，那么由于是从前往后枚举的，所以这种情况一定在搜索当前木棒的第一根木棍的分支中全部搜索过了，且已经发现无解了，而这个分支是要在当前搜索分支之前搜索的，所以这种情况也是不存在的。

​ （2.4）如果是木棒的最后一根木棍失败，则一定失败。

可以用反证法证明。当前木棍如果可以放在当前考察的木棒最后一个位置，但是最后不是一个合法方案，而该木棍放入到后面某个木棒中却成功了，此时我们仍然可以交换两者的位置，仍然是一种合法方案，矛盾。

（3）可行性剪枝：

​ （3.1）假设木棍的长度之和为sum，则必须满足length能被sum整除。

​ （3.2）如果将当前木棍放入当前木棒中，大于length，则不是合法方案。

（4）最优性剪枝：无。

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

using namespace std;

const int N = 70;

int n;
int w[N], sum, length;  // length: 枚举的木棒的长度
bool st[N];

// u: 当前枚举到的木棒编号; s: 当前木棒长度
// start: 当前枚举到的木棍编号
bool dfs(int u, int s, int start) {

    if (u * length == sum) return true;
    if (s == length) return dfs(u + 1, 0, 0);

    // 剪枝2-1，i从start开始枚举
    for (int i = start; i < n; i++) {
        if (st[i]) continue;
        if (s + w[i] > length) continue;  // 剪枝3-2: 可行性剪枝

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

        // 剪枝2-3
        if (!s) return false;

        // 剪枝2-4
        if (s + w[i] == length) return false;

        // 剪枝2-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];
        }

        // 剪枝1：优化搜索顺序
        sort(w, w + n);
        reverse(w, w + n);

        length = 1;
        while (true) {
            // 剪枝3-1: 可行性剪枝
            if (sum % length == 0 && dfs(0, 0, 0)) {
                cout << length << endl;
                break;
            }
            length++;
        }
    }

    return 0;
}