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

题目描述

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

输入描述: 

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

输出描述: 

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

备注: 

1≤N≤60

思路

先看N范围，1-60-->DFS，且大概率要剪枝，不剪枝大概率会TLE（事实也正是如此）
关于这题判断BFS，以及如何剪枝的思路，请看一楼大佬，传送门：经典剪枝题目——小木棍_牛客博客
判断与剪枝就不多说了，说说下面代码内部的逻辑
下面代码实际上是有三个地方判断tmp是否为合法长度
一是if(num==(sum/tmp) && len==0)这一句，意为：木棍已经全部拼接好，并且长度无剩余（注意！！！这里是根据拼接好的木棍条数与剩余长度来判断长度tmp是否合法！！）
二是if(len==0) break;这一句，意为：剪枝1：如果第i根木棍未被用上，那么之后肯定也不会被用上，说明tmp长度不合法
三是for(int i=pos;i<=n;i++)这整个循环语句，意为：判断第i根木棍的长度是否合法（即是否能被使用上）（注意！！！这里是根据具有a[i]长度的第i根木棍用上之后是否能够组成满足长度的木棍来判断长度tmp是否合法！！）
（其中这里面的while(a[i]==a[i+1]) i++;这一句算是这题里面最难懂的部分了，大致意思是：如果第i根木棍被用上了，那么与第i根木棍相同长度的木棍可以直接跳过（注意！！！这里可以跳过不是指这些木棍都一定可以拼接成tmp的长度！只是因为这里是根据具有a[i]长度的第i根木棍用上之后是否能够组成满足长度的木棍来判断长度tmp是否合法！！换句话说，就算出现这些木棍中的部分不可以拼接成tmp的长度，也会在上面的if(num==(sum/tmp) && len==0)的判断条件中被判为不合法！！））


代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,ans=0,flag=0,sum=0;
int a[70],vis[70];
int cmp(int a,int b) {
    return a>b;
}
void DFS(int tmp,int pos,int len,int num){ //tmp:当前的目标长度，pos:当前i开始的位置，len:当前第num根大木棍拼接的长度，num:第num根大木棍
    if(flag) return ;
    if(len==tmp){ //已经拼好一根木棍
        len=0;
        num++;
        pos=1;
    }
    if(num==(sum/tmp) && len==0){ //木棍已经全部拼接好，并且长度无剩余（注意！！！这里是根据拼接好的木棍条数与剩余长度来判断长度tmp是否合法！！）
        flag=1;
        printf("%d\n",tmp);
        return ;
    }
    for(int i=pos;i<=n;i++){ //判断第i根木棍的长度是否合法（即是否能被使用上）（注意！！！这里是根据具有a[i]长度的第i根木棍用上之后是否能够组成满足长度的木棍来判断长度tmp是否合法！！）
        if(len+a[i]>tmp || vis[i]) continue;
        vis[i]=1;
        DFS(tmp,i,len+a[i],num);
        vis[i]=0;
        if(len==0) break; //剪枝1：如果第i根木棍未被用上，那么之后肯定也不会被用上，说明tmp长度不合法，直接break
        while(a[i]==a[i+1]) i++; //剪枝2：如果第i根木棍被用上了，那么与第i根木棍相同长度的木棍可以直接跳过（注意！！！这里可以跳过不是指这些木棍都一定可以拼接成tmp的长度！只是因为这里是根据具有a[i]长度的第i根木棍用上之后是否能够组成满足长度的木棍来判断长度tmp是否合法！！换句话说，就算出现这些木棍中的部分不可以拼接成tmp的长度，也会在上面的if(num==(sum/tmp) && len==0)的判断条件中被判为不合法！！）
    }
    return ;
} 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    sort(a+1,a+1+n,cmp);
    for(int i=a[1];i<=sum;i++){
        if(sum%i!=0) continue;
        DFS(i,1,0,0);
        if(flag==1) break;
    }
    return 0;
}