P1120 小木棍

#include <bits/stdc++.h>
using namespace std;
vector<int> sticks;
vector<bool> used;
int n;
bool dfs (int cur, int target, int start, int cnt) {
	if (cnt == 0) return true;
	if (cur == target) {
		return dfs (0, target, 0, cnt - 1);
	}
	for (int i = start; i < n; ++i) {
		if (used [i] || cur + sticks [i] > target) continue;
		used [i] = true;
		if (dfs (cur + sticks [i], target, i + 1, cnt)) return true;
		used [i] = false;
		if (cur == 0 || cur + sticks [i] == target) break;
		while (i + 1 < n && sticks [i] == sticks [i + 1]) ++i;
	}
	return false;
}
int main () {
	cin >> n;
	sticks.resize (n);
	used.resize (n, false);
	int sum = 0, max_len = 0;
	for (int i = 0; i < n; ++i) {
		cin >> sticks [i];
		sum += sticks [i];
		max_len = max (max_len, sticks [i]);
	}
	sort (sticks.rbegin (), sticks.rend ());
	for (int len = max_len; len <= sum; ++len) {
		if (sum % len != 0) continue;
		fill (used.begin (), used.end (), false);
		if (dfs (0, len, 0, sum / len)) {
			cout << len << endl;
			return 0;
		}
	}
	cout << sum << endl;
	return 0;
}