1.题目基本信息
1.1.题目描述
给定你一个整数数组 nums
我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。
如果可以完成则返回true ， 否则返回 false 。
注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。
1.2.题目地址
https://leetcode.cn/problems/split-array-with-same-average/description/
2.解题方法
2.1.解题思路
思路1：二进制枚举+哈希表
-
易知移动之后，A数组和B数组都非空，且均值都等于nums的均值，则题目可以等价于nums中是否存在一个集合，其长度为k，且和为k*avg(nums)，从而将两个数组的问题转为一个数组的问题；
-
又由于avg(nums)中可能存在分数，所以可以将nums所有元素乘以n=len(nums)，然后减去sum(nums)，得到nums2，题目就等价于从nums2中找出一个集合，使其和为0。
-
将nums2分为两半，枚举前半部分的所有子集，每个子集进行求和，存储到集合set1中，后半部分枚举子集并求和，记为sum1，如果-sum1出现在set1中，则说明存在。
思路2：动态规划
2.2.解题步骤
二进制枚举+哈希表方法步骤：
-
第一步，记n=len(nums)，将nums中所有元素乘以n，并减去sum(nums)，得到nums2
-
第二步，枚举nums2的前半部分的子集，并求每个子集的和，记录到集合set1中
-
第三步，枚举nums2的后半部分的子集，并求和，记为sum1，如果-sum1出现在set1中，则说明存在，返回True
动态规划方法步骤：
-
第一步，剪枝。如果存在k个元素的和的平均值等于nums的平均值，即sum(nums)/n=sum1/k，则sum1=sum(nums)*k/n，且sum1为整数，所以枚举所有的k，如果不存在sum1为整数，则直接返回False
-
第二步，状态定义。dp[i]表示nums中i个元素的和所有的可能的值的集合；这里规定dp[i][x]=True为x在集合dp[i]中，False则表示不在集合dp[i]中
-
第三步，状态初始化。dp[0]=set([0])
-
第四步，状态转移。dp[i][x]=dp[i-1][x-num]。（注意：这里i的遍历一定需要逆序遍历，因为dp[i]依赖的是当前num前面的所有num状态下的dp[i-1]，如果将num的影响添加到dp[i-1]，那么dp[i]就不正确了）
-
第五步，如果存在dp[i][x]=True and isum(nums)==nx，则说明存在题目要求的组合
3.解题代码
二进制枚举方法代码
class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
# 思路1：二进制子集枚举+哈希表。易知移动之后，A数组和B数组都非空，且均值都等于nums的均值，则题目可以等价于nums中是否存在一个集合，其长度为k，且和为k*avg(nums)，从而将两个数组的问题转为一个数组的问题；又由于avg(nums)中可能存在分数，所以可以将nums所有元素乘以n=len(nums)，然后减去sum(nums)，得到nums2，题目就等价于从nums2中找出一个集合，使其和为0。将nums2分为两半，枚举前半部分的所有子集，每个子集进行求和，存储到集合set1中，后半部分枚举子集并求和，记为sum1，如果-sum1出现在set1中，则说明存在
# 第一步，记n=len(nums)，将nums中所有元素乘以n，并减去sum(nums)，得到nums2
n = len(nums)
if n == 1:
return False
totalSum = sum(nums)
nums2 = [t * n - totalSum for t in nums]
# 第二步，枚举nums2的前半部分的子集，并求每个子集的和，记录到集合set1中
n1 = n // 2
set1 = set()
for mask in range(1, 1 << n1):
sum1 = 0
for i in range(n1):
if (mask >> i) & 1 == 1:
sum1 += nums2[i]
if sum1 == 0:
return True
set1.add(sum1)
# print(set1)
# 第三步，枚举nums2的后半部分的子集，并求和，记为sum1，如果-sum1出现在set1中，则说明存在，返回True
n2 = n - n1
rsum = sum(nums2[n1:])
for mask in range(1, 1 << n2):
sum1 = 0
for i in range(n2):
if (mask >> i) & 1 == 1:
sum1 += nums2[n1 + i]
# 存在0元素时会触发前面的判断条件，导致返回True
if sum1 == 0 or (rsum != sum1 and -sum1 in set1):
return True
return False动态规划方法代码
class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
# 思路2：动态规划（0-1背包问题）
# 第一步，剪枝。如果存在k个元素的和的平均值等于nums的平均值，即sum(nums)/n=sum1/k，则sum1=sum(nums)*k/n，且sum1为整数，所以枚举所有的k，如果不存在sum1为整数，则直接返回False
n = len(nums)
n2 = n // 2
total = sum(nums)
if all([k * total % n != 0 for k in range(1, n + 1)]):
return False
# 第二步，状态定义。dp[i]表示nums中i个元素的和所有的可能的值的集合；这里规定dp[i][x]=True为x在集合dp[i]中，False则表示不在集合dp[i]中
dp = [set() for _ in range(n2 + 1)]
# 第三步，状态初始化。dp[0]=set([0])
dp[0].add(0)
# 第四步，状态转移。dp[i][x]=dp[i-1][x-num]。（注意：这里i的遍历一定需要逆序遍历，因为dp[i]依赖的是当前num前面的所有num状态下的dp[i-1]，如果将num的影响添加到dp[i-1]，那么dp[i]就不正确了）
for num in nums:
for i in range(n2, 0, -1):
for x1 in dp[i - 1]:
val = x1 + num
if i * total == n * val:
return True
dp[i].add(val)
# 第五步，如果存在dp[i][x]=True and i*sum(nums)==n*x，则说明存在题目要求的组合
return False4.执行结果
