链接：https://ac.nowcoder.com/acm/problem/50243
来源：牛客网

题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入描述: 

第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为N个用空格隔开的正整数，表示N根小木棍的长度。

输出描述: 

输出仅一行，表示要求的原始木棍的最小可能长度。
示例1

输入

复制  
9
5 2 1 5 2 1 5 2 1

输出

复制  
6

备注:

1≤N≤60

思路：

1.首先是判断sum能否整除枚举的长度（一下就可以省略很多没必要的步骤）
2.按木棍长从大到小放置，先放大的可以减少递归层数
3.如果这一根不行，那么下一根一样长的同样不行
4.如果这一层放的是最后一根或者第一根，结果不能符合条件，说明不是这一根出了问题，而是上一根出现问题，因为按长度排序，你放这一根或者是两根更小（和是一样的）没有区别。
代码: 
#include<bits/stdc++.h>
using namespace std;
int a[100],vis[100];
int n;
bool dfs(int num,int len,int rest, int last){
    if(rest==0&&num==0)return 1;
    if(rest==0){rest=len;last=0;}
    for(int i=last+1;i<=n;i++){
        if(vis[i])continue;
        if(a[i]>rest)continue;
        vis[i]=1;
        if(dfs(num-1,len,rest-a[i],i))return 1;
        vis[i]=0;
        if((a[i]==rest)||(rest==len))return 0;
        while(a[i]==a[i+1])i++;
    }
    return 0;
}
bool cmp(int a,int b){return a>b;}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
       
        sum+=a[i];
    }
//     cout<<maxm<<" "<<sum;
    sort(a+1,a+n+1,cmp);
    for(int i=a[1];i<=sum;i++){
        if(sum%i!=0)continue;
        if(dfs(n,i,i,0)){
            cout<<i;break;
        }
    }
    return 0;
}