This problem requires partitioning an integer array into two non-empty subsets with identical averages. A state transition dynamic programming approach tracks possible sums for each subset size, efficiently narrowing options. The challenge lies in balancing subset sizes while ensuring their sums align mathematically, leveraging bitmasking or DP for feasible combinations.
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
How GhostInterview Helps
- Generates step-by-step DP table for subset sum tracking specific to this array problem
- Highlights integer divisibility checks for subset averages to prevent wasted computation
- Visualizes subset selection paths and pruning decisions to quickly identify feasible splits
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Split Array With Same Average instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Split Array With Same Average from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count the number of squareful arrays from the given list of integers by checking adjacent pairs' sums for perfect squares.
Open problem page#1799 Maximize Score After N OperationsMaximize the score after n operations by selecting pairs from the array and using their GCD with dynamic programming or backtracking techniques.
Open problem page#698 Partition to K Equal Sum SubsetsDetermine if an integer array can be partitioned into k subsets where each subset sums to the same value using DP and backtracking.
Open problem page