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.
This approach involves using recursive backtracking to try and partition the array into two non-empty subsets with the same average. The key idea is to calculate the total sum and length of the numbers, and then explore the possibility of obtaining a subset.
If we choose a subset of k elements, their sum should be (k * total_sum) / n (where n is the total number of elements in the array).
We then recursively select or exclude elements to form such a sum and solve the problem.
The solution involves a recursive approach where the base case checks if the chosen subset has the correct average. We use memoization to avoid recalculating results for the same sums and subset sizes. The recursion tries every combination of elements, either including or excluding them from a subset being considered.
Time Complexity: O(2^n), where n is the length of the array, as we explore all subsets recursively.
Space Complexity: O(n^2) due to space used by memoization.
The dynamic programming approach calculates possibilities for reaching a given sum with a subset of a certain size. It iteratively builds possibilities using a dp table where indices represent possible sums and each entry keeps track of achievable sizes.
The aim is to check if any subset of size k has sum sum_k such that sum_k / k = total_sum / n.
This solution uses a 2D DP table to compute whether it's possible to form a subset of a given size with a specific sum. The table iteratively adds new numbers while ensuring subset inclusion is viable, checking each for valid average conditions.
C++
JavaScript
Time Complexity: O(n * total_sum), given double for loops dependent on these values.
Space Complexity: O(n * total_sum), for the dp table keeping track of subset sums and counts.
According to the problem requirements, we need to determine if the array nums can be divided into two subarrays A and B such that the average values of the two subarrays are equal.
Let the sum of the array nums be s, and the number of elements be n. The sum and number of elements of subarray A are s_1 and k, respectively. Then the sum of subarray B is s_2 = s - s_1, and the number of elements is n - k. Thus:
$
\frac{s_1}{k} = \frac{s_2}{n - k} = \frac{s-s_1}{n-k}
Rearranging, we get:
s_1 times (n-k) = (s-s_1) times k
Simplifying, we get:
\frac{s_1}{k} = \frac{s}{n}
This means we need to find a subarray A such that its average value equals the average value of the array nums. We consider subtracting the average value of the array nums from each element of the array nums, transforming the problem into finding a subarray in the array nums whose sum is 0.
However, the average value of the array nums may not be an integer, and floating-point calculations may have precision issues. We can multiply each element of the array nums by n, i.e., nums[i] \leftarrow nums[i] times n. The above equation becomes:
\frac{s_1times n}{k} = s
Now, we subtract the integer s from each element of the array nums, transforming the problem into finding a subarray A in the array nums whose sum is 0.
The length of the array nums ranges from [1, 30]. If we use brute force to enumerate subarrays, the time complexity is O(2^n), which will time out. We can use binary search to reduce the time complexity to O(2^{n/2}).
We divide the array nums into left and right parts. The subarray A can exist in three cases:
is entirely in the left part of the array nums; is entirely in the right part of the array nums; is partially in the left part and partially in the right part of the array nums.We can use binary enumeration to first enumerate the sums of all subarrays in the left part. If there is a subarray with a sum of 0, we return vistrue immediately. Otherwise, we store the sums in a hash table . Then we enumerate the sums of all subarrays in the right part. If there is a subarray with a sum of 0, we return vistrue immediately. Otherwise, we check if the hash table contains the opposite of the current sum. If it does, we return true.
Note that we cannot select all elements from both the left and right parts simultaneously, as this would leave subarray B empty, which does not meet the problem requirements. In implementation, we only need to consider n-1 elements of the array.
The time complexity is O(n times 2^{\frac{n}{2}}), and the space complexity is O(2^{\frac{n}{2}})$.
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(2^n), where n is the length of the array, as we explore all subsets recursively. Space Complexity: O(n^2) due to space used by memoization. |
| Dynamic Programming | Time Complexity: O(n * total_sum), given double for loops dependent on these values. Space Complexity: O(n * total_sum), for the dp table keeping track of subset sums and counts. |
| Binary Search + Binary Enumeration | — |
| 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 |
Leetcode 77 Problem 4 - Split Array With Same Average • code_report • 17,778 views views
Watch 9 more video solutions →Practice Split Array With Same Average with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor