24375: 小木棍

http://cs101.openjudge.cn/practice/24375/

小明将一批等长的木棍随机切成最长为50单位的小段。现在他想要将木棍还原成原来的状态，但是却忘记了原来的木棍数量和长度。请写一个程序帮助他计算如果还原成原来的等长木棍，其长度可能的最小值。所有的长度均大于0。

输入

输入包含多个实例。每个实例有两行，第一行是切割后的木棍数量n（最多64个），第二行为n个以空格分开的整数，分别为每根木棍的长度。输入的最后以n为 0 结束。

输出

对于每个实例，输出一行其长度的可能的最小值。

样例输入

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

样例输出

6
5

来源：来自计算概论B期末考试，本题对数据进行了弱化

与 https://github.com/GMyhf/2020fall-cs101 题集 2020fall_cs101.openjudge.cn_problems.md

中 Optional problems的 01011: Sticks 一样的题目，算法说明也在 01011。

#蒋子轩
def dfs(rem_sticks,rem_len,target):
    if rem_sticks==0 and rem_len==0:
        return True
    if rem_len==0:
        rem_len=target
    for i in range(n):
        if not used[i] and lens[i]<=rem_len:
            used[i]=True
            if dfs(rem_sticks-1,rem_len-lens[i],target):
                return True
            else:
                used[i]=False
                if lens[i]==rem_len or rem_len==target:
                    return False
    return False
while True:
    n=int(input())
    if n==0:
        break
    lens=list(map(int,input().split()))
    lens.sort(reverse=True)
    total_len=sum(lens)
    for l in range(lens[0],total_len//2+1):
        if total_len%l!=0:
            continue
        used=[False]*n
        if dfs(n,l,l):
            print(l)
            break
    else:
        print(total_len)