http://acm.pku.edu.cn/JudgeOnline/problem?id=1011
Код:
#include <iostream> #include <algorithm> #define MAXN 64 using namespace std; int N, LEN, M; int S[MAXN], MK[MAXN]; bool FLAG; int cmp(int a, int b) { return a > b; } void dfs(int k, int sum, int cnt) { if (cnt == M) FLAG = true; else if (sum == LEN) dfs(0, 0, cnt+1); else for (int pre = -1, i = k; i < N; i++) if (!MK[i] && S[i]!=pre && S[i]+sum<=LEN) { pre = S[i]; MK[i] = true; dfs(i+1, sum+S[i], cnt); MK[i] = false; if (k == 0 || FLAG) return; } } int main() { int sum, i; while (scanf("%d", &N) != EOF && N) { FLAG = false; sum = 0; for (i = 0; i < N; i++) { scanf("%d", &S[i]); sum += S[i]; } sort(S, S+N, cmp); for (LEN = S[0]; LEN < sum; LEN++) if (sum % LEN == 0) { M = sum / LEN; memset(MK, 0, sizeof(MK)); dfs(0, 0, 0); if (FLAG) break; } printf("%d\n", FLAG? LEN : sum); } return 0; }