Split Array With Same Average
Split Array With Same Average is a hard dynamic programming problem solved with the knapsack pattern.
The best approach, optimal (meet in the middle on zero-sum subsets), runs in O(2^(n/2) · n) time and O(2^(n/2)) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (every subset) up.
Problem
You are given an integer array nums. Move every element into exactly one of two groups A and B so that both groups are non-empty and the average of A equals the average of B.
Return true if such a split exists, and false otherwise. (The average of a group is the sum of its elements divided by how many there are.)
Examples
Example 1
- Input
nums = [1, 2, 3, 4, 5, 6]- Output
true- Why
- Put [1, 6] in one group and [2, 3, 4, 5] in the other; both averages are 3.5.
Example 2
- Input
nums = [2, 9, 4]- Output
false- Why
- The overall average is 5, but no single element or pair of elements averages exactly 5.
Example 3
- Input
nums = [8, 8]- Output
true- Why
- Each group holds one 8, so both averages are 8.
Constraints
1 <= nums.length <= 300 <= nums[i] <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every subset) | O(2^n · n) | O(1) |
| Better (subset-sum DP by size) | O(n² · total) | O(n · total) |
| Optimal (meet in the middle on zero-sum subsets) | O(2^(n/2) · n) | O(2^(n/2)) |
1Brute force (every subset)
O(2^n · n)There are 2^n masks and each one is summed in O(n).O(1)Only counters.Enumerate every non-empty proper subset with a bitmask. A subset of size cnt and sum sum has the same average as the whole array exactly when sum * n == total * cnt, and then its complement has that average too.
- total = sum of nums.
- For mask from 1 to 2^n - 2: compute cnt and sum of the chosen elements.
- If sum * n == total * cnt, return true.
- Return false.
class Solution {
public boolean splitArraySameAverage(int[] nums) {
int n = nums.length;
long total = 0;
for (int x : nums) total += x;
for (int mask = 1; mask < (1 << n) - 1; mask++) {
long sum = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
if ((mask >> i & 1) == 1) {
sum += nums[i];
cnt++;
}
}
if (sum * n == total * cnt) return true;
}
return false;
}
}class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
total = sum(nums)
for mask in range(1, (1 << n) - 1):
s = 0
cnt = 0
for i in range(n):
if mask >> i & 1:
s += nums[i]
cnt += 1
if s * n == total * cnt:
return True
return Falseclass Solution {
public:
bool splitArraySameAverage(vector<int>& nums) {
int n = nums.size();
long long total = 0;
for (int x : nums) total += x;
for (int mask = 1; mask < (1 << n) - 1; mask++) {
long long sum = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) {
sum += nums[i];
cnt++;
}
}
if (sum * n == total * cnt) return true;
}
return false;
}
};function splitArraySameAverage(nums) {
const n = nums.length;
let total = 0;
for (const x of nums) total += x;
for (let mask = 1; mask < (1 << n) - 1; mask++) {
let sum = 0, cnt = 0;
for (let i = 0; i < n; i++) {
if ((mask >> i) & 1) {
sum += nums[i];
cnt++;
}
}
if (sum * n === total * cnt) return true;
}
return false;
}2Better (subset-sum DP by size)
O(n² · total)n elements times n / 2 sizes times up to total sums.O(n · total)The (n / 2 + 1) x (total + 1) boolean table.A subset of size k works exactly when its sum is total * k / n, which must be a whole number. Only sizes up to n / 2 matter, because the complement of a working subset also works. Build a table dp[k][s] = can some k elements sum to s, adding one element at a time like a 0/1 knapsack.
- If no k in [1, n / 2] makes total * k divisible by n, return false.
- dp[0][0] = true. For each x, for k from n / 2 down to 1, for s from total down to x: dp[k][s] |= dp[k - 1][s - x].
- Return true if some k has total * k % n == 0 and dp[k][total * k / n].
class Solution {
public boolean splitArraySameAverage(int[] nums) {
int n = nums.length, half = n / 2, total = 0;
for (int x : nums) total += x;
boolean possible = false;
for (int k = 1; k <= half; k++) {
if (total * k % n == 0) possible = true;
}
if (!possible) return false;
boolean[][] dp = new boolean[half + 1][total + 1];
dp[0][0] = true;
for (int x : nums) {
for (int k = half; k >= 1; k--) {
for (int s = total; s >= x; s--) {
if (dp[k - 1][s - x]) dp[k][s] = true;
}
}
}
for (int k = 1; k <= half; k++) {
if (total * k % n == 0 && dp[k][total * k / n]) return true;
}
return false;
}
}class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
half = n // 2
total = sum(nums)
if not any(total * k % n == 0 for k in range(1, half + 1)):
return False
dp = [[False] * (total + 1) for _ in range(half + 1)]
dp[0][0] = True
for x in nums:
for k in range(half, 0, -1):
prev, cur = dp[k - 1], dp[k]
for s in range(total, x - 1, -1):
if prev[s - x]:
cur[s] = True
for k in range(1, half + 1):
if total * k % n == 0 and dp[k][total * k // n]:
return True
return Falseclass Solution {
public:
bool splitArraySameAverage(vector<int>& nums) {
int n = nums.size(), half = n / 2, total = 0;
for (int x : nums) total += x;
bool possible = false;
for (int k = 1; k <= half; k++) {
if (total * k % n == 0) possible = true;
}
if (!possible) return false;
vector<vector<char>> dp(half + 1, vector<char>(total + 1, 0));
dp[0][0] = 1;
for (int x : nums) {
for (int k = half; k >= 1; k--) {
for (int s = total; s >= x; s--) {
if (dp[k - 1][s - x]) dp[k][s] = 1;
}
}
}
for (int k = 1; k <= half; k++) {
if (total * k % n == 0 && dp[k][total * k / n]) return true;
}
return false;
}
};function splitArraySameAverage(nums) {
const n = nums.length, half = Math.floor(n / 2);
let total = 0;
for (const x of nums) total += x;
let possible = false;
for (let k = 1; k <= half; k++) {
if ((total * k) % n === 0) possible = true;
}
if (!possible) return false;
const dp = Array.from({ length: half + 1 }, () => new Uint8Array(total + 1));
dp[0][0] = 1;
for (const x of nums) {
for (let k = half; k >= 1; k--) {
for (let s = total; s >= x; s--) {
if (dp[k - 1][s - x]) dp[k][s] = 1;
}
}
}
for (let k = 1; k <= half; k++) {
if ((total * k) % n === 0 && dp[k][(total * k) / n]) return true;
}
return false;
}3Optimal (meet in the middle on zero-sum subsets)
O(2^(n/2) · n)Each half has at most 2^15 masks, and each mask is summed in O(n).O(2^(n/2))The set of left-half subset sums.Replace each value with a[i] = nums[i] * n - total. A subset has the whole array's average exactly when its a-values sum to 0, and the whole a array sums to 0. So the task becomes: find a non-empty proper subset with sum 0. Split the indices into a left half and a right half (at most 15 each) and enumerate the subset sums of each half. A zero-sum subset either lies in one half (checked directly) or combines a left part with a right part whose sums cancel. Keeping only proper left subsets in the lookup set guarantees the combined subset is proper; the case that needs the full left half is covered by the right-half check on the complement.
- If n == 1, return false. Build a[i] = nums[i] * n - total.
- h = n / 2. For each non-empty left mask: if its sum is 0, return true; if the mask is not the full left half, add the sum to a set.
- For each non-empty right mask with sum s: if s == 0 or the set contains -s, return true.
- Return false.
class Solution {
public boolean splitArraySameAverage(int[] nums) {
int n = nums.length;
if (n == 1) return false;
int total = 0;
for (int x : nums) total += x;
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nums[i] * n - total;
int h = n / 2, m = n - h;
Set<Integer> left = new HashSet<>();
for (int mask = 1; mask < (1 << h); mask++) {
int s = 0;
for (int i = 0; i < h; i++) {
if ((mask >> i & 1) == 1) s += a[i];
}
if (s == 0) return true;
if (mask != (1 << h) - 1) left.add(s);
}
for (int mask = 1; mask < (1 << m); mask++) {
int s = 0;
for (int i = 0; i < m; i++) {
if ((mask >> i & 1) == 1) s += a[h + i];
}
if (s == 0 || left.contains(-s)) return true;
}
return false;
}
}class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return False
total = sum(nums)
a = [x * n - total for x in nums]
h = n // 2
m = n - h
left = set()
full = (1 << h) - 1
for mask in range(1, 1 << h):
s = 0
for i in range(h):
if mask >> i & 1:
s += a[i]
if s == 0:
return True
if mask != full:
left.add(s)
for mask in range(1, 1 << m):
s = 0
for i in range(m):
if mask >> i & 1:
s += a[h + i]
if s == 0 or -s in left:
return True
return Falseclass Solution {
public:
bool splitArraySameAverage(vector<int>& nums) {
int n = nums.size();
if (n == 1) return false;
int total = 0;
for (int x : nums) total += x;
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = nums[i] * n - total;
int h = n / 2, m = n - h;
unordered_set<int> left;
for (int mask = 1; mask < (1 << h); mask++) {
int s = 0;
for (int i = 0; i < h; i++) {
if (mask >> i & 1) s += a[i];
}
if (s == 0) return true;
if (mask != (1 << h) - 1) left.insert(s);
}
for (int mask = 1; mask < (1 << m); mask++) {
int s = 0;
for (int i = 0; i < m; i++) {
if (mask >> i & 1) s += a[h + i];
}
if (s == 0 || left.count(-s)) return true;
}
return false;
}
};function splitArraySameAverage(nums) {
const n = nums.length;
if (n === 1) return false;
let total = 0;
for (const x of nums) total += x;
const a = nums.map((x) => x * n - total);
const h = Math.floor(n / 2), m = n - h;
const left = new Set();
for (let mask = 1; mask < (1 << h); mask++) {
let s = 0;
for (let i = 0; i < h; i++) {
if ((mask >> i) & 1) s += a[i];
}
if (s === 0) return true;
if (mask !== (1 << h) - 1) left.add(s);
}
for (let mask = 1; mask < (1 << m); mask++) {
let s = 0;
for (let i = 0; i < m; i++) {
if ((mask >> i) & 1) s += a[h + i];
}
if (s === 0 || left.has(-s)) return true;
}
return false;
}Edge cases to test
- A single element: it cannot be split into two non-empty groups
- All values equal: any split works
- One element equal to the overall average, like [1, 2, 3]
- Many zeros mixed with one large value
Hints
Hint 1
If both groups have the same average, that average must equal the average of the whole array.
Hint 2
So you only need one non-empty proper subset of size k whose sum is exactly total * k / n, and k can be limited to at most n / 2.
Hint 3
Subtract the average from every value (scale by n to stay in integers). Now you need a non-empty proper subset summing to 0, and 2^30 subsets can be split into two halves of 2^15 each.
FAQ
What is the best time complexity for Split Array With Same Average?
Optimal (meet in the middle on zero-sum subsets) runs in O(2^(n/2) · n) time and O(2^(n/2)) extra space. Each half has at most 2^15 masks, and each mask is summed in O(n).
Which pattern does Split Array With Same Average use?
It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.
Is there a brute force solution for Split Array With Same Average?
Yes. Brute force (every subset) takes O(2^n · n) time and O(1) space. Enumerate every non-empty proper subset with a bitmask.
Which edge cases should I test for Split Array With Same Average?
A single element: it cannot be split into two non-empty groups; All values equal: any split works; One element equal to the overall average, like [1, 2, 3]; Many zeros mixed with one large value.