README_CN.md

805. 数组的均值分割

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回true ， 否则返回 false 。

**注意：**对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。

示例 1:

输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

示例 2:

输入: nums = [3,1]
输出: false

提示:

• 1 <= nums.length <= 30
• 0 <= nums[i] <= 104

题解 (Python)

1. 题解

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        if len(nums) < 2:
            return False

        s = sum(nums)
        sums = [set() for _ in range(len(nums) // 2 + 1)]
        sums[0].add(0)

        for num in nums:
            for i in range(len(sums) - 2, -1, -1):
                for x in sums[i]:
                    if (x + num) * len(nums) == s * (i + 1):
                        return True

                    sums[i + 1].add(x + num)

        return False