Partition Array Into Two Arrays to Minimize Sum Difference

hard dp meet in the middle bitmask

Problem

You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays. Return the minimum possible absolute difference.

Inputnums = [3,9,7,3]

Output2

n = 2. Choosing {3,9} vs {7,3} gives sums 12 and 10, difference 2. We pick n items in total and want the chosen sum as close to total/2 as possible.

nums (length 2n)

from bisect import bisect_left, insort

def minimum_difference(nums):
    n = len(nums) // 2
    total = sum(nums)
    A, B = nums[:n], nums[n:]
    # group subset sums of each half by how many elements chosen
    def sums_by_count(half):
        m = len(half)
        groups = [[] for _ in range(m + 1)]
        for mask in range(1 << m):
            cnt = bin(mask).count("1")
            s = sum(half[i] for i in range(m) if mask & (1 << i))
            groups[cnt].append(s)
        return groups
    GA, GB = sums_by_count(A), sums_by_count(B)
    best = float("inf")
    for k in range(n + 1):
        right = sorted(GB[n - k])
        for sa in GA[k]:
            # pick k from A, n-k from B; want left close to total/2
            target = total / 2 - sa
            j = bisect_left(right, target)
            for cand in (right[j - 1] if j else None, right[j] if j < len(right) else None):
                if cand is None:
                    continue
                left = sa + cand
                best = min(best, abs(total - 2 * left))
    return best

function minimumDifference(nums) {
  const n = nums.length / 2, total = nums.reduce((a, b) => a + b, 0);
  const A = nums.slice(0, n), B = nums.slice(n);
  function sumsByCount(half) {
    const m = half.length, groups = Array.from({ length: m + 1 }, () => []);
    for (let mask = 0; mask < (1 << m); mask++) {
      let cnt = 0, s = 0;
      for (let i = 0; i < m; i++) if (mask & (1 << i)) { cnt++; s += half[i]; }
      groups[cnt].push(s);
    }
    return groups;
  }
  const GA = sumsByCount(A), GB = sumsByCount(B);
  let best = Infinity;
  for (let k = 0; k <= n; k++) {
    const right = GB[n - k].slice().sort((a, b) => a - b);
    for (const sa of GA[k]) {
      const target = total / 2 - sa;
      let lo = 0, hi = right.length;
      while (lo < hi) { const mid = (lo + hi) >> 1; if (right[mid] < target) lo = mid + 1; else hi = mid; }
      for (const j of [lo - 1, lo]) {
        if (j < 0 || j >= right.length) continue;
        const left = sa + right[j];
        best = Math.min(best, Math.abs(total - 2 * left));
      }
    }
  }
  return best;
}

class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length / 2, total = 0;
        for (int x : nums) total += x;
        List<List<Integer>> GA = sums(nums, 0, n), GB = sums(nums, n, n);
        int best = Integer.MAX_VALUE;
        for (int k = 0; k <= n; k++) {
            List<Integer> right = GB.get(n - k);
            Collections.sort(right);
            for (int sa : GA.get(k)) {
                int target = total / 2 - sa;
                int lo = lowerBound(right, target);
                for (int j : new int[]{lo - 1, lo}) {
                    if (j < 0 || j >= right.size()) continue;
                    int left = sa + right.get(j);
                    best = Math.min(best, Math.abs(total - 2 * left));
                }
            }
        }
        return best;
    }
    private List<List<Integer>> sums(int[] nums, int start, int m) {
        List<List<Integer>> g = new ArrayList<>();
        for (int c = 0; c <= m; c++) g.add(new ArrayList<>());
        for (int mask = 0; mask < (1 << m); mask++) {
            int cnt = 0, s = 0;
            for (int i = 0; i < m; i++) if ((mask & (1 << i)) != 0) { cnt++; s += nums[start + i]; }
            g.get(cnt).add(s);
        }
        return g;
    }
    private int lowerBound(List<Integer> a, int t) {
        int lo = 0, hi = a.size();
        while (lo < hi) { int mid = (lo + hi) >>> 1; if (a.get(mid) < t) lo = mid + 1; else hi = mid; }
        return lo;
    }
}

int minimumDifference(vector<int>& nums) {
    int n = nums.size() / 2, total = 0;
    for (int x : nums) total += x;
    auto sums = [&](int start, int m) {
        vector<vector<int>> g(m + 1);
        for (int mask = 0; mask < (1 << m); mask++) {
            int cnt = __builtin_popcount(mask), s = 0;
            for (int i = 0; i < m; i++) if (mask & (1 << i)) s += nums[start + i];
            g[cnt].push_back(s);
        }
        return g;
    };
    auto GA = sums(0, n), GB = sums(n, n);
    int best = INT_MAX;
    for (int k = 0; k <= n; k++) {
        auto& right = GB[n - k];
        sort(right.begin(), right.end());
        for (int sa : GA[k]) {
            int target = total / 2 - sa;
            int j = lower_bound(right.begin(), right.end(), target) - right.begin();
            for (int t : {j - 1, j}) {
                if (t < 0 || t >= (int)right.size()) continue;
                int left = sa + right[t];
                best = min(best, abs(total - 2 * left));
            }
        }
    }
    return best;
}

Explanation

We must put exactly n of the 2n numbers on the left. If the left sum is L, the right sum is total - L and the difference is |total - 2L|. So we want L as close as possible to total / 2, while choosing exactly n elements.

Trying all subsets is 2^(2n) — too many. Meet in the middle halves the exponent: split the array into two halves A and B. Within each half we enumerate every subset and bucket its sum by how many elements it used, giving groups[count].

To form a left side of size n we take k elements from A and n - k from B. For a fixed sum sa from A's k-bucket, the ideal partner from B is the one making sa + sb closest to total / 2.

So we sort each of B's buckets and binary search for target = total/2 - sa, checking the two neighbours around it. Each gives a candidate left sum; we keep the smallest |total - 2L| overall. That turns an exponential search into roughly 2^n * n work.

Example: [3,9,7,3], n = 2, total 22, half 11. The closest reachable left sum with 2 elements is 12 (e.g. 3+9), giving |22 - 24| = 2 — the minimum difference.

Time: O(2ⁿ·n) for 2n elements Space: O(2ⁿ)