题意：一开始有n根同样的小木棍，后来将其切成长度不超过50的小木棍，问原来小木棍最短长度是多少。
例如砍完后有四根，长度分别为1，2，3，4，原来长度可能为5，或10。5是最小可能长度。

分析：可以用深搜，符合深搜要素：
1临界条件：凑成n根相同木棍退出。
2当前只需考虑当前选择：就是我们可以计算他有多少种可能（长度数量）。然后每次加一种，当组成一条时候，长度清零，凑成根数++。

这道题就比较清晰了，用dfs做，+剪枝（减少搜索时间避免超时）。
做题思路：
1、输入所有木棍长度存到a[n]，并算出总和sum。进行降序排序（先排大的，减少可能性，因为小的更灵活）
2、遍历从a[1]到sum/2切前木棍长度在这个可能性区间（剪枝，因为最小木棍long肯定>=max(a[i])，如果切前木棍都不在这个区间则切前木棍是sum）
3、计算出切前棍子数量tot和每根长度
4、对于区间内每一个符合的情况，dfs（数量，长度，上次的从哪开始）（剪枝）

实现代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[105],book[105];
int n,m,x,sum,len,tot,flag;

bool cmp(int a,int b){return a>b;}

void dfs(int k, int now, int las)
{
    if(flag)return;//全部退出
    if(k==tot)  //临界条件；
    {
        flag = 1;//标志，
        printf("%d\n",len);
        return ;
    }

    for( int i=las; i <= n; i++)//有n-last种可能（），前面的拿过了，不用理
    {
        if(book[i]) continue;
        if(now + a[i] <len)//分两种情况深搜等于，和不等于，因为代码不一样
        {
            book[i] = 1;
            dfs(k,now + a[i],i);//没凑够在凑成的长度里面加上这次的长度
            book[i] = 0;
        }
        else if(now+a[i]==len)
        {
            book[i] = 1;
            dfs(k+1,0,0);//凑够一根了根数++，从头来
            book[i] = 0;
        }
        if(now == 0 || now + a[i] == len) return ;
        while(a[i + 1] == a[i]) i++;//在同一深度的搜索里面（同一个for下），深搜同一个数毫无意义。除非，这是第一次搜索或者快下次搜索
    }
}

int main()
{
    int num,i;
    while(cin>>n&&n)
    {
        sum = 0; m = 0; flag = 0;
        for(i = 1; i <= n; i++)
        {
            cin>>num;
            if(num <= 50)a[i]=num,sum += num;//所有之和，棍子所长必为sum的因数
        }
        sort(a+1,a+n+1,cmp);//倒序减低搜索深度
        for(i = a[1]; i <= sum / 2; i++)
        {
            if(sum%i) continue;//保证，i是sum的因数
            memset(book,0,sizeof(book));
            tot=sum/i; len = i; flag = 0;
            dfs(0,0,1);
            if(flag) break;//flag=1表示找到最小的了，（我们从下往上找必为，第一个找到必最小）
        }
        if(!flag) printf("%d\n",sum);//如果全部没有，输入sum即只有一根
    }
    return 0;
}