回溯算法----MVP争夺战（93通过率）

题目描述
在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者。

可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，

然而比赛过程中的每1分钟的得分都只能由某一个人包揽。

输入描述
输入第一行为一个数字 t ，表示为有得分的分钟数

1 ≤ t ≤ 50
第二行为 t 个数字，代表每一分钟的得分 p，

1 ≤ p ≤ 50
输出描述
输出有得分的队员都是MVP时，最少得MVP得分。

用例1
输入
9
5 2 1 5 2 1 5 2 1
输出
6
说明
样例解释 一共 4 人得分，分别都是 6 分

5 + 1 ， 5 + 1 ， 5 + 1 ， 2 + 2 + 2

#https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solutions/1441006/by-lfool-d9o7/
#参考lc上698题，划分为k个相等的子集
t = int(input())
scores = list(map(int,input().split()))

scores.sort(reverse=True) # 降序排序，优先使用较大的数字
numbers=[] #存放可能的MVP数量
for num in range(1,t+1):
    #平分后的分数和不能小于某一个单独时间段的分数
    if sum(scores)%num==0 and sum(scores)//num>=max(scores):
        numbers.append(num)
numbers.sort(reverse=True)
def backtrack(index,bucket,target):#index表示第几个成绩做选择，bucket：集合
    global k
    if index ==len(scores):#已经遍历完所有的分数
        return True
    for i in range(k):
        if i>0 and bucket[i]==bucket[i-1]:# 避免重复计算相同的分组
            continue
        if bucket[i]+scores[index]>target:#当前数字无法加入当前分组
            continue
        bucket[i]+=scores[index] #将当前数字加入分组中
        if backtrack(index+1,bucket,target):#递归尝试下一个数字
            return True
        bucket[i]-=scores[index] #回溯，尝试另一个组合
    return False
for k in numbers:
    bucket=[0]*k
    target = sum(scores)//k
    if backtrack(0,bucket,target):
        print(target)
        break