发一道老早写的题。
1 #include<iostream>
2 #include <algorithm>
3 using namespace std;
4 int a[65];
5 bool use[65];
6 int n,m,len;
7 int cmp(int a, int b)
8 {
9 return a > b;
10 }
11 bool dfs(int i,int sum,int j)
12 {
13 int k,temp,x;
14 if(j==m) return 1;
15 else if(sum==len) return dfs(1,0,j+1);
16 else
17 {
18 temp=-1;
19 for(k=i;k<=n;k++)
20 if(!use[k]&&a[k]<=len-sum&&a[k]!=temp)
21 {
22 temp=a[k];
23 use[k]=1;
24 x=dfs(k+1,sum+a[k],j);
25 use[k]=0;
26 if(x==1) return 1;
27 if(i==1) return 0;
28 }
29 }
30 return 0;
31 }
32 int main()
33 {
34 int sum;
35 int i,j;
36 cin>>n;
37 while(n!=0)
38 {
39 for(i=1;i<=n;i++) cin>>a[i];
40 sort(a+1, a+n+1, cmp);
41 sum=0;
42 for(i=1;i<=n;i++) sum=a[i]+sum;
43 for(len=a[1];len<sum;len++)
44 if(sum%len==0)
45 {
46 memset(use,0,sizeof(use));
47 m=sum/len;
48 if(dfs(1,0,1)) break;
49 }
50 cout<<len<<endl;
51 cin>>n;
52 }
53 }