搜索

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, INF = 0x3f3f3f3f;
int n, a[N], len, cnt;
bool st[N];

// dfs(now,length,last)
// 当前正在拼第now根原始木棒,且已经拼出长度length,上次使用的木棒last
bool dfs(int now, int length, int last) {
    if (now > cnt)
        return true;
    if (length == len)
        return dfs(now + 1, 0, 1);
    int fail = 0;
    for (int i = last; i <= n; i++) {
        if (!st[i] && length + a[i] <= len && fail != a[i]) {
            st[i] = 1;
            if (dfs(now, length + a[i], i + 1))
                return true;
            st[i] = 0, fail = a[i];
            if (length == 0 || length + a[i] == len)
                return false;
        }
    }
    return false;
}
int main() {
    int sum = 0, val = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    sort(a + 1, a + 1 + n, greater<int>());
    for (len = a[n]; len <= sum; len++) {
        if (sum % len) continue;
        cnt = sum / len;
        memset(st, 0, sizeof st);
        if (dfs(1, 0, 1)) break;
    }
    cout << len << endl;
    return 0;
}