Pattern Reference
Meet in the Middle
"Split the input in half, solve each half, combine results. Subset sum, knapsack, TSP."
Loading...
Deep Dive Tutorial
When n ≈ 40, brute-force 2^40 is too slow but DP is hard or doesn't apply. Meet in the middle: split into two halves of ~20 elements each. Enumerate all 2^20 subsets of each half, generating their sums/states. Sort one half's results. For each element in the other half's results, binary search for the complement. Total: O(2^(n/2) · n) instead of O(2^n).
Meet in the middle template — subset sum
// Count subsets with sum = target
// n up to 40: too slow for 2^40, but 2*2^20 is fine
function countSubsets(nums, target) {
const n = nums.length;
const half = n >> 1;
const left = nums.slice(0, half);
const right = nums.slice(half);
// Enumerate all subset sums for left half
const leftSums = [];
for (let mask = 0; mask < (1 << left.length); mask++) {
let sum = 0;
for (let i = 0; i < left.length; i++) if ((mask >> i) & 1) sum += left[i];
leftSums.push(sum);
}
leftSums.sort((a, b) => a - b);
// For each right half subset, binary search for complement in left
let count = 0;
for (let mask = 0; mask < (1 << right.length); mask++) {
let sum = 0;
for (let i = 0; i < right.length; i++) if ((mask >> i) & 1) sum += right[i];
const need = target - sum;
// Count leftSums entries equal to need
const lo = lowerBound(leftSums, need);
const hi = upperBound(leftSums, need);
count += hi - lo;
}
return count;
}Worked Problems
handshake
When to use MITM:
- n ≈ 40 (2^40 too slow, 2^20 fine)
- Subset sum, counting subsets with property
- Optimization over all subsets
Template:
1. Split input in half
2. Enumerate all 2^(n/2) subsets of each half
3. Sort one half's results
4. For each result in other half: binary search for complement
Complexity: O(2^(n/2) · n) instead of O(2^n)
Grouping trick: For problems needing "take exactly k elements," group subset sums by count k. Then for each k in left half, look at right half sums[target_count - k] — avoids invalid pairings.
- n ≈ 40 (2^40 too slow, 2^20 fine)
- Subset sum, counting subsets with property
- Optimization over all subsets
Template:
1. Split input in half
2. Enumerate all 2^(n/2) subsets of each half
3. Sort one half's results
4. For each result in other half: binary search for complement
Complexity: O(2^(n/2) · n) instead of O(2^n)
Grouping trick: For problems needing "take exactly k elements," group subset sums by count k. Then for each k in left half, look at right half sums[target_count - k] — avoids invalid pairings.