题目描述

给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。

输入描述

第一行输入 m

接着输入m个数，表示此数组nums

数据范围：1<=m<=50, 1<=nums[i]<=50

输出描述

最小拆分数组和

测试样例1

输入

7
4 3 2 3 5 2 1

输出

5

说明

可以等分的情况有：

4 个子集（5），（1,4），（2,3），（2,3）

2 个子集（5, 1, 4），（2,3, 2,3）

但最小的为5。

Python代码解析

def min_group_sum(nums):
    total = sum(nums)
    min_sum = 50 * 50 + 1

    def backtrack(index, m, sum, num_groups, total_sum):
        nonlocal min_sum
        if sum == target:
            total_sum += sum
            if total_sum == target * num_groups:
                if sum < min_sum:
                    min_sum = sum
            else:
                backtrack(0, m, 0, num_groups - 1, total_sum)
        else:
            for i in range(index, m):
                if sum + nums[i] <= target:
                    temp = nums[i]
                    nums[i] = -1
                    backtrack(i + 1, m, sum + temp, num_groups, total_sum)
                    nums[i] = temp

    nums.sort(reverse=True)
    m = len(nums)
    for num_groups in range(1, m + 1):
        if total % num_groups == 0:
            target = total // num_groups
            backtrack(0, m, 0, num_groups, 0)

    return min_sum


if __name__ == "__main__":
    nums = [4, 3, 2, 3, 5, 2, 1]
    print(min_group_sum(nums))

参考

https://wiki.amoscloud.com/zh/ProgramingPractice/NowCoder/Adecco/Topic0236