[AcWing 167] 木棒

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
int w[N];
int sum, len;
bool st[N];

bool dfs(int u, int s, int start)
{
    if (u * len == sum)
        return true;
    if (s == len)
        return dfs(u + 1, 0, 0);
    // 排除等效冗余 按照组合数枚举
    for (int i = start; i < n; i ++) {
        // 可行性剪枝
        if (st[i] || s + w[i] > len)
            continue;
        st[i] = true;
        if (dfs(u, s + w[i], i + 1))
            return true;
        st[i] = false;
        // 排除等效冗余 放到头尾失败则失败
        if (!s || s + w[i] == len)
            return false;
        // 排除等效冗余 排除掉相同值的元素
        int j = i;
        while (j < n && w[j] == w[i])
                j ++;
        i = j - 1;
    }
    return false;
}

void solve()
{
    while (cin >> n, n) {
        memset(st, false, sizeof st);
        sum = 0;
        for (int i = 0; i < n; i ++) {
            cin >> w[i];
            sum += w[i];
        }
        // 优化搜索顺序 从大到小排序
        sort(w, w + n, greater<int>());
        len = 1;
        while (true) {
            // 可行性剪枝
            if (sum % len == 0 && dfs(0, 0, 0)) {
                cout << len << endl;
                break;
            }
            len ++;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}