Meet in the Middle

How to think about it

Meet in the middle is the trick that saves subset-enumeration when 2^n is too big but 2^(n/2) is not. Split the array in half. Enumerate all 2^(n/2) subsets of the left half, storing their sums (or any aggregate) in a sorted list or hash map. Then enumerate all 2^(n/2) subsets of the right half; for each, compute the complement you need and look it up in the left structure. The key: 2 * 2^(n/2) is dramatically smaller than 2^n - at n=40, 2^40 is a trillion but 2 * 2^20 is two million.

The merge step depends on the query: for “closest sum to target”, sort the left sums and binary-search the complement of each right sum. For “count subsets summing to target”, use a hash map of left sums to counts. For “partition with constraints”, the right enumeration filters against the left.

Template shapes

Shape	Core move	Example
Closest sum	Left sums sorted; binary search complement per right subset	LC 1755, LC 2035
Count subsets	Left sums in hash map; sum counts per right subset	LC 1655
Partition with min diff	Both halves; sort left; for each right, find best left	LC 2035
Constraint satisfaction	Encode state per half; match on join key	LC 1601

Complexity baseline

O(2^(n/2) * n/2) to enumerate each half. O(2^(n/2) * log(2^(n/2))) to sort + query. Total: O(n * 2^(n/2)) time, O(2^(n/2)) space. At n=40, that is about 2 * 10^7, feasible.

From template to problem

1. Confirm n is in the ~30-45 sweet spot, smaller, use brute force; larger, need a different technique.
2. Split the input into two halves of roughly equal size.
3. Enumerate all subsets of each half, storing the relevant aggregate.
4. Sort or hash one half; for each subset of the other half, look up the complement.
5. Be careful with double-counting: the empty subset on one side combined with the empty on the other is the empty set, count or exclude it as the problem requires.

/** Meet in the middle template: closest subset sum to target. */

export function closestSubsetSum(nums: number[], target: number): number {
  const n = nums.length;
  const mid = Math.floor(n / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const leftSums = new Set<number>([0]);
  for (const v of left) {
    for (const s of [...leftSums]) leftSums.add(s + v);
  }
  const sorted = [...leftSums].sort((a, b) => a - b);

  let best = 0;
  const rightSums = [0];
  for (const v of right) {
    for (const s of [...rightSums]) rightSums.push(s + v);
  }
  for (const r of rightSums) {
    const need = target - r;
    let lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
      const m = (lo + hi + 1) >> 1;
      if (sorted[m]! <= need) lo = m;
      else hi = m - 1;
    }
    if (Math.abs(r + sorted[lo]! - target) < Math.abs(best - target)) {
      best = r + sorted[lo]!;
    }
  }
  return best;
}

/** Meet in the middle template: closest subset sum to target. */

export function closestSubsetSum(nums: number[], target: number): number {
  const n = nums.length;
  const mid = Math.floor(n / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const leftSums = new Set<number>([0]);
  for (const v of left) {
    for (const s of [...leftSums]) leftSums.add(s + v);
  }
  const sorted = [...leftSums].sort((a, b) => a - b);

  let best = 0;
  const rightSums = [0];
  for (const v of right) {
    for (const s of [...rightSums]) rightSums.push(s + v);
  }
  for (const r of rightSums) {
    const need = target - r;
    let lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
      const m = (lo + hi + 1) >> 1;
      if (sorted[m]! <= need) lo = m;
      else hi = m - 1;
    }
    if (Math.abs(r + sorted[lo]! - target) < Math.abs(best - target)) {
      best = r + sorted[lo]!;
    }
  }
  return best;
}