1 #include<iostream> 2 #include<algorithm> 3 #define maxn  70 4 using namespace std; 5 int stick[maxn]; 6 bool visit[maxn]; 7 int length,pos,num,n,sum; 8 int cmp(int x,int y) 9 {10     return x>y ;11 }12 bool dfs(int count,int now,int pos)13 {14     int i;15     bool sign=(now==0?true:false);//标记当前长度16     if(count==num) return true;17     for(i=pos;i<n;i++)18     {19         if(visit[i]) continue;//用过了就不用考虑了20         if(now+stick[i]==length)21         {22             visit[i]=true;//标记棍子是否使用23             if(dfs(count+1,0,0))//已经完成当前棍子匹配,进行下一根棍子的的匹配24                 return true;25             visit[i]=false;//无法完成匹配,则应重置26             return false;27         }28     29         else if(now+stick[i]<length)30         {31             visit[i]=true;32             if(dfs(count,now+stick[i],i))//继续搜索没有用过的棍子以完成匹配33                 return true;34             visit[i]=false;35             if(sign) return false;//长度为0说明当前长度匹配不成功,继续下一个长度的搜索;36             while(stick[i]==stick[i+1]) i++;//重要剪枝,相同长度的棍子没必要再搜索37         }38 }39   return false;40         41 }42 int main()43 {44     //freopen("1455.txt","r",stdin);45     int i;46     while(~scanf("%d",&n),n)47     {48         sum=0;49         for(i=0;i<n;i++)50             scanf("%d",stick+i),sum+=stick[i];51         sort(stick,stick+n,cmp);//从大到小排;52         for(length=stick[0];length<=sum;length++)53         {54             if(sum%length==0)55             {56                 num=sum/length;57                 memset(visit,false,sizeof(visit));58                 if(dfs(1,0,0))59                 {60                     printf("%d\n",length);61                     break;62                 }63             }64         }65     }66         return 0;67     }