⚡Flashcard Drill➔
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

  1. Equal averages mean sum(A) / |A| = total / n, which cross-multiplies to the integer test sum(A) * n == total * |A|.
  2. So it suffices to know, for each subset size k, which sums are achievable; a subset of size k and sum s works when s * n == total * k.
  3. Because a valid split has one part of size at most n // 2 (the smaller side), only k up to n // 2 needs to be enumerated.
  4. Build possible[k] = set of achievable sums with k elements 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 * k to avoid precision errors.
  • Enumerating all 2^n subsets: n up 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 k upward 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems