Watch 10 video solutions for Split Array With Same Average, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by code_report has 17,778 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
You should move each element of nums into one of the two arrays A and B such that A and B are non-empty, and average(A) == average(B).
Return true if it is possible to achieve that and false otherwise.
Note that for an array arr, average(arr) is the sum of all the elements of arr over the length of arr.
Example 1:
Input: nums = [1,2,3,4,5,6,7,8] Output: true Explanation: 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
Constraints:
1 <= nums.length <= 300 <= nums[i] <= 104Problem Overview: You need to determine whether an integer array can be split into two non-empty groups such that both groups have the same average. If the total sum is S and array length is n, the task becomes finding a subset of size k whose sum equals (S * k) / n.
Approach 1: Recursive Backtracking with Pruning (Exponential time, O(2^n) time, O(n) space)
This approach tries all possible subsets using recursion. For each subset size k, compute the required target sum (S * k) / n. If this value is not an integer, skip that subset size immediately. Otherwise recursively choose elements and track the running sum and count. Sorting the array allows early pruning when the remaining elements cannot reach the required sum. The recursion explores inclusion and exclusion of elements until a valid subset is found. This method demonstrates the mathematical insight behind the problem but becomes slow as n grows.
Approach 2: Dynamic Programming with Bitmask / Subset Sum (O(n^2 * sum) time, O(n * sum) space)
A more efficient strategy converts the problem into a constrained subset-sum dynamic programming task. Instead of checking every subset, maintain DP states where dp[k] stores possible sums achievable using exactly k elements. Iterate through the array and update these states in reverse order to avoid reuse of elements. For each size k, check if the sum (S * k) / n exists in the stored sums. If such a state appears, a valid split exists. Bitsets or hash sets can store reachable sums efficiently. This technique avoids enumerating all subsets and relies on incremental state transitions, which is much faster in practice.
The key mathematical insight is that equal averages imply equal ratios between subset sum and subset size. Instead of directly comparing averages, transform the requirement into a subset sum constraint.
This problem combines ideas from Array, Math, and Dynamic Programming. Bitmask-style state tracking also appears in many subset enumeration problems.
Recommended for interviews: The dynamic programming approach is typically expected because it shows you understand how to convert an average constraint into a subset-sum formulation. Explaining the backtracking version first demonstrates reasoning about the search space, while the DP optimization shows strong problem-solving and algorithm design skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Pruning | O(2^n) | O(n) | Useful for understanding subset formation and applying pruning on small arrays |
| Dynamic Programming (Subset Sum by Size) | O(n^2 * sum) | O(n * sum) | General optimized solution that avoids enumerating all subsets |