Split Array With Same Average

hard dp meet-in-the-middle subset-sum math

Problem

Given integer array nums, return true if you can split it into two non-empty subsets A and B (each element used exactly once) so that average(A) == average(B).

Inputnums = [1,2,3,4,5,6,7,8]

Outputtrue

[1,4,5,8] and [2,3,6,7] both have average 4.5.

nums

def splitArraySameAverage(nums):
    n = len(nums); s = sum(nums)
    if not any(s * k % n == 0 for k in range(1, n // 2 + 1)):
        return False
    half = n // 2
    left = nums[:half]; right = nums[half:]
    sums_left = [set() for _ in range(half + 1)]
    for mask in range(1 << len(left)):
        cnt, tot = bin(mask).count('1'), 0
        for i in range(len(left)):
            if mask & (1 << i): tot += left[i]
        sums_left[cnt].add(tot)
    sums_right = [set() for _ in range(len(right) + 1)]
    for mask in range(1 << len(right)):
        cnt, tot = bin(mask).count('1'), 0
        for i in range(len(right)):
            if mask & (1 << i): tot += right[i]
        sums_right[cnt].add(tot)
    for k in range(1, n):
        if s * k % n: continue
        target = s * k // n
        for kl in range(max(0, k - len(right)), min(len(left), k) + 1):
            if k == n and kl == len(left): continue
            for v in sums_left[kl]:
                if (target - v) in sums_right[k - kl]:
                    return True
    return False

var splitArraySameAverage = function(nums) {
    const n = nums.length, s = nums.reduce((a,b)=>a+b,0);
    let possible = false;
    for (let k = 1; k <= Math.floor(n/2); k++) if ((s*k) % n === 0) { possible = true; break; }
    if (!possible) return false;
    const half = Math.floor(n/2);
    const left = nums.slice(0, half), right = nums.slice(half);
    const build = (arr) => {
        const out = Array.from({length: arr.length+1}, () => new Set());
        for (let m = 0; m < (1<<arr.length); m++) {
            let c = 0, t = 0;
            for (let i = 0; i < arr.length; i++) if (m & (1<<i)) { c++; t += arr[i]; }
            out[c].add(t);
        }
        return out;
    };
    const L = build(left), R = build(right);
    for (let k = 1; k < n; k++) {
        if ((s*k) % n) continue;
        const target = (s*k)/n;
        for (let kl = Math.max(0, k - right.length); kl <= Math.min(left.length, k); kl++) {
            if (k === n && kl === left.length) continue;
            for (const v of L[kl]) if (R[k-kl].has(target - v)) return true;
        }
    }
    return false;
};

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length, s = 0;
        for (int x : nums) s += x;
        boolean possible = false;
        for (int k = 1; k <= n/2; k++) if ((s*k) % n == 0) { possible = true; break; }
        if (!possible) return false;
        int half = n/2;
        java.util.List<java.util.Set<Integer>> L = build(nums, 0, half);
        java.util.List<java.util.Set<Integer>> R = build(nums, half, n);
        for (int k = 1; k < n; k++) {
            if ((s*k) % n != 0) continue;
            int target = s*k/n;
            for (int kl = Math.max(0, k - (n - half)); kl <= Math.min(half, k); kl++) {
                if (k == n && kl == half) continue;
                for (int v : L.get(kl)) if (R.get(k - kl).contains(target - v)) return true;
            }
        }
        return false;
    }
    private java.util.List<java.util.Set<Integer>> build(int[] nums, int lo, int hi) {
        int len = hi - lo;
        java.util.List<java.util.Set<Integer>> out = new java.util.ArrayList<>();
        for (int i = 0; i <= len; i++) out.add(new java.util.HashSet<>());
        for (int m = 0; m < (1<<len); m++) {
            int c = 0, t = 0;
            for (int i = 0; i < len; i++) if ((m & (1<<i)) != 0) { c++; t += nums[lo+i]; }
            out.get(c).add(t);
        }
        return out;
    }
}

class Solution {
    vector<unordered_set<int>> build(vector<int>& nums, int lo, int hi) {
        int len = hi - lo;
        vector<unordered_set<int>> out(len + 1);
        for (int m = 0; m < (1<<len); m++) {
            int c = 0, t = 0;
            for (int i = 0; i < len; i++) if (m & (1<<i)) { c++; t += nums[lo+i]; }
            out[c].insert(t);
        }
        return out;
    }
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size(), s = accumulate(nums.begin(), nums.end(), 0);
        bool possible = false;
        for (int k = 1; k <= n/2; k++) if ((s*k) % n == 0) { possible = true; break; }
        if (!possible) return false;
        int half = n/2;
        auto L = build(nums, 0, half), R = build(nums, half, n);
        for (int k = 1; k < n; k++) {
            if ((s*k) % n != 0) continue;
            int target = s*k/n;
            for (int kl = max(0, k - (n - half)); kl <= min(half, k); kl++) {
                if (k == n && kl == half) continue;
                for (int v : L[kl]) if (R[k - kl].count(target - v)) return true;
            }
        }
        return false;
    }
};

Explanation

The first move is a bit of algebra. If subset A has k elements with the same average as the whole array, then sum(A) must equal s·k/n where s is the total sum and n the length. So the question becomes: is there a subset of some size k whose sum is exactly target = s·k/n? If no k even makes s·k divisible by n, the answer is immediately false.

Checking all subsets is 2^n, too slow, so we use meet in the middle. Split the array into a left half and a right half. For each half, enumerate every subset and record its sum, grouped by how many elements it used: sums_left[count] and sums_right[count].

Now for each target size k we try every split kl + kr = k across the two halves. We need a left subset of size kl summing to some v and a right subset of size kr = k - kl summing to target - v. Because the right sums live in a hash set, that lookup is instant.

Example: nums = [1..8], sum 36, n 8. Picking k = 4 gives target = 36·4/8 = 18. The subset [1,4,5,8] sums to 18, so it and the remaining [2,3,6,7] both average 4.5 — answer true.

Splitting in half turns the cost from 2^n into roughly 2^(n/2) per half, which is the whole point of meet in the middle.

Time: O(n * 2^(n/2)) Space: O(2^(n/2))