剪枝好题，具体见代码：

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7  8 inline int read() 9 {10     int f=1,x=0; char ch;11     while(!isdigit(ch=getchar())) if(ch=='-') f=-1;12     while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 16 #define res register int17 const int N=100;18 int a[N],used[N],n,sum,m,ok,len;19 bool cmp(const int &x,const int &y){
    return x>y;}20 21 void dfs(int now,int last,int rest)22 {23     if(rest==0)24     {    25         int i;26         if(now==m) {ok=1; return ;}27         for(i=1 ; i<=n ; i++) if(!used[i]) break;28         used[i]=1; dfs(now+1,i,len-a[i]);29         used[i]=0; if(ok) return ;30     }31     32     for(res i=last+1 ; i<=n ; i++)33     {34         if(!used[i]&&a[i]<=rest)35         {36             used[i]=1;    dfs(now,i,rest-a[i]);    used[i]=0;37             if(ok)    return ;38             while(a[i+1]==a[i]) i++;//39             if(rest==len||rest==a[i]) return ; 40         }41         if(i==n) return ; 42     }43 }44 45 /*剪枝：46 1.把小木棍从大到小排序，先拼大的47 2.从小到大枚举原始木块长度len,成立了就直接输出答案。范围：最短的木棍到所有木棍48 长度之和的一半，且len需要整除sum49 3.当一个木棍不能拼时，和它长度相等的木棍显然也不能拼50 4.枚举下一个要拼的木棍时只需从上一个用过的木块的下一个开始枚举51 ****5.如果当前长棍剩余的未拼长度等于当前正在试着拼的木块的长度或者等于原始长度（即52 刚开始拼），继续拼下去却失败了，则直接回溯，结束枚举。 53 */ 54 int main()55 {56 57     while(scanf("%d",&n)==1 && n)58     {59         sum=0;ok=0;60         memset(used,0,sizeof(used));61         memset(a,0,sizeof(a));62         for(res i=1 ; i<=n ; i++)63         {64             a[i]=read();65             sum+=a[i];66         }67         sort(a+1,a+n+1,cmp);68         for(len=a[1] ; len<=sum/2+1 ; len++)69         {70             if(sum%len!=0) continue;71              used[1]=1; m=sum/len;72             ok=0;73              dfs(1,1,len-a[1]);74              used[1]=0;75             if(ok) 76             {77                     printf("%d\n",len);78                     break;79             }80         }81         if(!ok) printf("%d\n",sum);82     }83     return 0;84 }