题解 | #小木棍#

#include<bits/stdc++.h>
using namespace std;

int a[70], v[70];
int sum,n;

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

int dfs(int num, int len, int rest, int last)
{
    if ((num == 0) && (rest == 0)) return 1;
    if (rest == 0) rest = len, last = 0;
    for (int i = last + 1; i<=n; i++)
    {
        if (v[i]) continue;
        if (a[i] > rest) continue;
        v[i] = 1;
        if (dfs(num - 1, len, rest - a[i], i)) return 1;
        v[i] = 0;
        if ((a[i] == rest) || (rest == len)) return 0;//*剪枝部分*
        while (a[i] == a[i + 1]) i++;//*剪枝部分*
    }

    return 0;
}

int main() 
{
    int i;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + 1 + n, cmp);
    for (i = a[1]; i <= sum; i++) {
        if (sum % i != 0) continue;
        if (dfs(n, i, i, 0)) {
            cout << i << endl;
            break;
        }
    }
}