1011 sticks DFS

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[100],b[10];
 5 int main(){
 6     int n,sum,maxn=0,h=0,k=0;
 7     while(cin>>n){
 8         if(n==0)
 9             break;
10         sum=0;
11         for(int i=0;i<n;i++){
12             cin>>a[i];
13             if(a[i]>maxn)
14                 maxn=a[i];
15             sum+=a[i];
16         }
17         for(int i=maxn;i<=sum;i++)
18             if(sum%i==0){
19                 b[h++]=i;
20                 k=h;
21                 break;
22             }
23     }
24     for(int i=0;i<k;i++)
25         cout<<b[i]<<endl;
26     return 0;
27 }

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define N 100
 6 int n, coun, sum;
 7 int vis[N], e[N];
 8 bool cmp(int a, int b)
 9 {
10     return a > b;
11 }
12 int dfs(int L, int sum, int t)
13 {
14     if(sum == L && t == n) return 1;
15     if(sum == L) sum = 0;
16     for(int i = 0; i < n; i++){
17         if(i > 0 && !vis[i-1] && e[i] == e[i-1]) continue;//第六条剪枝
18         if(vis[i] || sum+e[i] > L) continue;
19         vis[i] = 1;
20         if(dfs(L, sum+e[i], t+1)) return 1;
21         else{
22             vis[i] = 0;
23             if(!sum || sum == L) return 0;//第四第五条的剪枝
24         }
25     }
26     return 0;
27 }
28 
29 int main()
30 {
31     int i, j, ans;
32     while(scanf("%d", &n), n){
33         for(i = ans = 0; i < n; i++){
34             scanf("%d", &e[i]);
35             ans += e[i];
36         }
37         sort(e, e+n, cmp);//第三条
38         for(i = e[0]; i <= ans/2; i++){//第一条剪枝
39             if(ans%i != 0) continue;//第二条剪枝
40             memset(vis, 0, sizeof(vis));
41             if(dfs(i, 0, 0)){
42                 printf("%d\n", i);
43                 break;
44             }
45         }
46         if(i > ans/2) printf("%d\n", ans);
47     }
48     return 0;
49 }