Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Partition Array Into Two Arrays to Minimize Sum Difference

Problem (restated)

nums has length 2n (n ≤ 15). Split into two arrays of length n. Minimize |sum(first) − sum(second)|.

Intuition

|sum1 − sum2| = |2·sum1 − total|, and sum1 must use exactly n elements. C(2n, n) is too big; each half has n ≤ 15 items, so enumerate all subsets of each half grouped by size.

Approaches

Meet in the middle, sums by size

Unverified

Time O(n·2^n)Space O(2^n)

Idea. Split into two halves of n. Bucket every subset sum by cardinality k. For a left subset of size k, binary-search a right subset of size n−k closest to total/2 − leftSum (check the floor index and lo+1). Values may be negative; sorted buckets still work.

Walkthrough. [3,9,7,3]: halves [3,9] and [7,3]. Size-1 match 3+7=10 vs total 22 → diff 2. [-36,36] cannot split to 0: each side must take one element → 72.

Trade-offs. Subset-sum DP fails: values reach ±1e7 and the count constraint is exact n. MITM is the intended scale.

Solution

export function minimumDifference(nums: number[]): number {
  const n = nums.length >> 1;
  const left = nums.slice(0, n);
  const right = nums.slice(n);
  const total = nums.reduce((a, b) => a + b, 0);

  const sumsBySize = (arr: number[]): number[][] => {
    const m = arr.length;
    const buckets: number[][] = Array.from({ length: m + 1 }, () => []);
    for (let mask = 0; mask < 1 << m; mask++) {
      let s = 0, k = 0;
      for (let i = 0; i < m; i++) {
        if (mask & (1 << i)) {
          s += arr[i]!;
          k++;
        }
      }
      buckets[k]!.push(s);
    }
    for (const b of buckets) b.sort((a, b) => a - b);
    return buckets;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const L = sumsBySize(left);
  const R = sumsBySize(right);
  let ans = Number.MAX_SAFE_INTEGER;
  for (let k = 0; k <= n; k++) {
    const rightSums = R[n - k]!;
    for (const ls of L[k]!) {
      const rs = closest(rightSums, (total - 2 * ls) >> 1);
      const diff = Math.abs(2 * (ls + rs) - total);
      if (diff < ans) ans = diff;
    }
  }
  return ans;
}

export function minimumDifference(nums: number[]): number {
  const n = nums.length >> 1;
  const left = nums.slice(0, n);
  const right = nums.slice(n);
  const total = nums.reduce((a, b) => a + b, 0);

  const sumsBySize = (arr: number[]): number[][] => {
    const m = arr.length;
    const buckets: number[][] = Array.from({ length: m + 1 }, () => []);
    for (let mask = 0; mask < 1 << m; mask++) {
      let s = 0, k = 0;
      for (let i = 0; i < m; i++) {
        if (mask & (1 << i)) {
          s += arr[i]!;
          k++;
        }
      }
      buckets[k]!.push(s);
    }
    for (const b of buckets) b.sort((a, b) => a - b);
    return buckets;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const L = sumsBySize(left);
  const R = sumsBySize(right);
  let ans = Number.MAX_SAFE_INTEGER;
  for (let k = 0; k <= n; k++) {
    const rightSums = R[n - k]!;
    for (const ls of L[k]!) {
      const rs = closest(rightSums, (total - 2 * ls) >> 1);
      const diff = Math.abs(2 * (ls + rs) - total);
      if (diff < ans) ans = diff;
    }
  }
  return ans;
}

Template connection

Closest-sum MITM plus a cardinality join: left size k with right size n−k. Empty-vs-full is illegal here — initialize the answer to ∞, not |total|.

Reflection

The array length is 2n. Each half has n elements. Bucket subset sums by how many elements they use. For a left subset of size k, search the right buckets of size n - k for the sum closest to total / 2 - left.
The two pieces have equal length. The difference is |total - 2 * subset|. The empty choice and the full choice differ by the total.
Negatives are fine as long as each bucket stays sorted. Each half produces 2**n sums.