NeetCode #760LC-805Hard2-D Dynamic Programming
← Back to All Problems#760 · #805 · Split Array With Same Average(数组的均值分割)
📌 Problem Statement & Constraints
Given an integer array
nums, return true if it can be split into two non-empty subsets whose averages are equal. Constraints: 1 <= nums.length <= 30, 0 <= nums[i] <= 10^4.💡 Core Algorithmic Approaches
- Equal averages mean
sum(A) / |A| = total / n, which cross-multiplies to the integer testsum(A) * n == total * |A|. - So it suffices to know, for each subset size
k, which sums are achievable; a subset of sizekand sumsworks whens * n == total * k. - Because a valid split has one part of size at most
n // 2(the smaller side), onlykup ton // 2needs to be enumerated. - Build
possible[k]= set of achievable sums withkelements using a 0/1 knapsack over the elements.
💻 Benchmark Python3 Implementation
class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
total = sum(nums)
half = n // 2
# possible[k] = all sums achievable with exactly k elements
possible = [set() for _ in range(half + 1)]
possible[0].add(0)
for v in nums:
for k in range(half, 0, -1): # descending: each element once
for s in possible[k - 1]:
possible[k].add(s + v)
for k in range(1, half + 1):
if total * k % n == 0 and (total * k // n) in possible[k]:
return True
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * (n/2) * distinct sums): a 0/1 knapsack over sizes and achievable sums.
💾 Space Complexity
O((n/2) * distinct sums): the sets of achievable sums.
⚠️ Interview Pitfalls & Follow-ups
- Comparing floating-point averages: use the cross-multiplied integer test
s * n == total * kto avoid precision errors. - Enumerating all 2^n subsets:
nup to 30 makes that too slow; the size-and-sum DP collapses it. - Checking only
k == n // 2: the two parts need not be equal in size, only equal in average. - Iterating
kupward in the knapsack: that would reuse an element; the descending loop keeps each element used at most once.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.