• What is Meet-in-the-Middle?
• Subset Sum and Variants
• k-Sum via Meet-in-the-Middle
• Optimizations and Tricks
• Exercises

Meet-in-the-middle (MitM) splits the problem into two halves, enumerates partial results for each half, and then combines them efficiently. It reduces O(c^n) brute force to roughly O(c^{n/2}) time and memory, often using sorting, hashing, or two-pointers.

• Typical gain: from O(2^n) to O(2^{n/2})
• Tradeoff: time-memory tradeoff (store half-enumerations)
• Use cases: subset sum, k-sum, knapsack approximation, some crypto attacks

// MitM subset sum: does any subset sum to T?
function subsetSumMitM(a, T) {
  const n = a.length, m = n >> 1;
  const L = a.slice(0, m), R = a.slice(m);
  const sumsL = [];
  const sumsR = [];
  // enumerate all sums of left half
  for (let mask = 0; mask < (1 << L.length); mask++) {
    let s = 0; for (let i = 0; i < L.length; i++) if (mask & 1 << i) s += L[i];
    sumsL.push(s);
  }
  // enumerate all sums of right half
  for (let mask = 0; mask < (1 << R.length); mask++) {
    let s = 0; for (let i = 0; i < R.length; i++) if (mask & 1 << i) s += R[i];
    sumsR.push(s);
  }
  sumsR.sort((x,y) => x - y);
  for (const s of sumsL) {
    const need = T - s;
    // binary search for need in sumsR
    let l = 0, r = sumsR.length - 1;
    while (l <= r) {
      const m = l + ((r - l) >> 1);
      if (sumsR[m] === need) return true;
      if (sumsR[m] < need) l = m + 1; else r = m - 1;
    }
  }
  return false;
}

// 4-sum in O(n^2 log n) using MitM
function fourSumExists(a, T) {
  const pairs = [];
  for (let i = 0; i < a.length; i++) {
    for (let j = i + 1; j < a.length; j++) {
      pairs.push(a[i] + a[j]);
    }
  }
  pairs.sort((x,y) => x - y);
  for (let i = 0; i < pairs.length; i++) {
    const need = T - pairs[i];
    // binary search need
    let l = 0, r = pairs.length - 1;
    while (l <= r) {
      const m = l + ((r - l) >> 1);
      if (pairs[m] === need) return true;
      if (pairs[m] < need) l = m + 1; else r = m - 1;
    }
  }
  return false;
}

• Prune: avoid adding sums exceeding T when all numbers are non-negative.
• Compression: deduplicate sums using Map/Set to keep arrays small.
• Signed numbers: use hash sets rather than two-pointer on sorted arrays.
• Reconstruction: store back-pointers or masks if you need the actual subset.

1. Meet-in-the-middle knapsack: approximate 0/1 knapsack with n ≤ 40.
2. k-sum existence for k=5 using hashing of 2-sum and 3-sum lists.
3. Count the number of subsets summing to T (not just existence).