#805

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Split Array With Same Average

Determine whether an integer array can be partitioned into two non-empty subarrays with the same average using dynamic programming.

array math dynamic programming bit manipulation bitmask

Problem Statement

Given an integer array nums, determine if it is possible to split it into two non-empty arrays A and B such that the average of A equals the average of B. Each element must belong to exactly one of the two arrays.

Return true if such a split exists, otherwise return false. For example, nums = [1,2,3,4,5,6,7,8] can be split into [1,4,5,8] and [2,3,6,7], both averaging 4.5, while nums = [3,1] cannot be split to satisfy this condition.

Examples

Example 1

Input: nums = [1,2,3,4,5,6,7,8]

Output: true

We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have an average of 4.5.

Example 2

Input: nums = [3,1]

Output: false

Example details omitted.

Constraints

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

Solution Approach

Transform the problem using total sum and subset sizes

Compute the total sum of nums and consider that for any split, subset A with size k must have sum s = total_sum * k / n. Only integer sums are feasible, which immediately prunes impossible subset sizes.

Dynamic programming via state transition

Use DP where dp[i] is the set of achievable sums using i elements. Iteratively update dp[i+1] by adding each number in nums to sums in dp[i], capturing all possible subset sums for each size. This efficiently explores valid splits.

Early pruning and bitmask optimization

If the total sum times k modulo n is not zero, skip that k. Optionally, use bitmasking to track reachable sums for each subset size, reducing memory and improving runtime compared to naive enumeration.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * 2^n) in naive recursion but can be reduced using DP and bitmask optimization; space complexity is O(n * sum) to store achievable subset sums for each subset size.

What Interviewers Usually Probe

Looking for DP with careful state definition and sum tracking
Expect candidates to notice integer divisibility constraints
Interested in optimization via subset sum pruning or bitmask representation

Common Pitfalls or Variants

Common pitfalls

Overlooking non-integer average feasibility for subset sizes
Using naive recursion without pruning leading to TLE
Failing to consider empty subsets, which are invalid

Follow-up variants

Find all possible splits rather than returning true/false
Allow splitting into more than two subarrays with the same average
Restrict subsets to contiguous elements while maintaining equal averages

FAQ

What is the main pattern used in Split Array With Same Average?

State transition dynamic programming is the primary approach, tracking achievable sums for each subset size.

Can this problem be solved without DP?

Naive recursion is possible but inefficient; DP with pruning is required to pass larger test cases.

Why is integer divisibility important here?

Because only subset sums that are integers can produce valid averages matching the total array average.

What is the expected time complexity with DP and pruning?

Time complexity is significantly reduced from O(n*2^n) to feasible levels, depending on array sum and size, often acceptable for n <= 30.

Does GhostInterview provide code examples for this problem?

Yes, it guides through DP table construction, subset sum tracking, and pruning logic specific to Split Array With Same Average.

terminal

Solution

Solution 1: Binary Search + Binary Enumeration

According to the problem requirements, we need to determine if the array $\textit{nums}$ can be divided into two subarrays $A$ and $B$ such that the average values of the two subarrays are equal.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return False
        s = sum(nums)
        for i, v in enumerate(nums):
            nums[i] = v * n - s
        m = n >> 1
        vis = set()
        for i in range(1, 1 << m):
            t = sum(v for j, v in enumerate(nums[:m]) if i >> j & 1)
            if t == 0:
                return True
            vis.add(t)
        for i in range(1, 1 << (n - m)):
            t = sum(v for j, v in enumerate(nums[m:]) if i >> j & 1)
            if t == 0 or (i != (1 << (n - m)) - 1 and -t in vis):
                return True
        return False

Continue Practicing

#996 number of squareful arrays #1799 maximize score after n operations #698 partition to k equal sum subsets