Meet in the Middle Pattern
1. Two Array Sum Combination Problem
| Concept | Description | Use Case | Complexity |
|---|---|---|---|
| Core Idea | Split search space into two halves, enumerate all possibilities in each half, then combine results | Reduce exponential O(2^n) to O(2^(n/2)) | O(2^(n/2)) |
| Two Array Sum | Generate all sums from first half, search for complement in second half sums | Find pair from two arrays with target sum | O(2^(n/2) log 2^(n/2)) |
| Hash Map Approach | Store all sums from one half in hash map, check complements from other half | Fast lookup for combination existence | O(2^(n/2)) |
| Two Pointers | Sort both halves' sums, use two pointers from opposite ends | Find all pairs or closest pair to target | O(2^(n/2) log 2^(n/2)) |
Example: Find if subset sum equals target using two arrays
function canPartitionToTarget(arr, target) {
const n = arr.length;
const mid = Math.floor(n / 2);
// Generate all subset sums for first half
function generateSums(start, end) {
const sums = [];
const size = end - start;
for (let mask = 0; mask < (1 << size); mask++) {
let sum = 0;
for (let i = 0; i < size; i++) {
if (mask & (1 << i)) {
sum += arr[start + i];
}
}
sums.push(sum);
}
return sums;
}
const leftSums = generateSums(0, mid);
const rightSums = generateSums(mid, n);
// Sort right sums for binary search
rightSums.sort((a, b) => a - b);
// For each left sum, check if complement exists in right
for (const leftSum of leftSums) {
const needed = target - leftSum;
// Binary search for needed value
let left = 0, right = rightSums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (rightSums[mid] === needed) {
return true;
} else if (rightSums[mid] < needed) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
console.log(canPartitionToTarget([1, 3, 5, 7, 9, 11], 15)); // true
console.log(canPartitionToTarget([1, 3, 5, 7, 9, 11], 100)); // false2. Subset Sum Using Split Search
| Pattern | Technique | Application | Optimization |
|---|---|---|---|
| Split Into Halves | Divide array into two equal/near-equal parts | Reduce search space from O(2^n) to O(2^(n/2)) | Significant for n > 20 |
| Generate All Subsets | Use bit manipulation to enumerate all 2^(n/2) subsets | Each subset represents a possible sum | Store in array or set |
| Combine Results | For each subset sum from first half, search complement in second half | Use binary search or hash set for O(log n) or O(1) lookup | Sort one half for binary search |
| Count Solutions | Use hash map to count frequency of each sum | Count number of ways to achieve target sum | Multiply frequencies from both halves |
Example: Count number of subsets with given sum
function countSubsetsWithSum(arr, target) {
const n = arr.length;
const mid = Math.floor(n / 2);
// Generate subset sums with frequencies
function generateSumFrequency(start, end) {
const freqMap = new Map();
const size = end - start;
for (let mask = 0; mask < (1 << size); mask++) {
let sum = 0;
for (let i = 0; i < size; i++) {
if (mask & (1 << i)) {
sum += arr[start + i];
}
}
freqMap.set(sum, (freqMap.get(sum) || 0) + 1);
}
return freqMap;
}
const leftSums = generateSumFrequency(0, mid);
const rightSums = generateSumFrequency(mid, n);
let count = 0;
// For each left sum, find matching right sum
for (const [leftSum, leftFreq] of leftSums) {
const needed = target - leftSum;
if (rightSums.has(needed)) {
count += leftFreq * rightSums.get(needed);
}
}
return count;
}
console.log(countSubsetsWithSum([1, 2, 3, 4, 5], 7));
// Output: 3 (subsets: {2,5}, {3,4}, {1,2,4})3. Closest Subset Sum Problem
| Problem Type | Strategy | Data Structure | Time Complexity |
|---|---|---|---|
| Closest to Target | Generate all sums from both halves, find pair with minimum difference from target | Sorted arrays + two pointers | O(2^(n/2) log 2^(n/2)) |
| Two Pointer Scan | Sort both sum arrays, use pointers from opposite ends to minimize |left + right - target| | Two sorted arrays | O(2^(n/2)) |
| Binary Search | For each left sum, binary search for closest right sum to make target | One sorted array | O(2^(n/2) log 2^(n/2)) |
| Track Min Diff | Maintain global minimum difference while scanning combinations | Variable for best result | Same as search |
Example: Find subset sum closest to target
function closestSubsetSum(arr, target) {
const n = arr.length;
const mid = Math.floor(n / 2);
function generateSums(start, end) {
const sums = [];
const size = end - start;
for (let mask = 0; mask < (1 << size); mask++) {
let sum = 0;
for (let i = 0; i < size; i++) {
if (mask & (1 << i)) {
sum += arr[start + i];
}
}
sums.push(sum);
}
return sums;
}
const leftSums = generateSums(0, mid);
const rightSums = generateSums(mid, n);
// Sort both arrays
leftSums.sort((a, b) => a - b);
rightSums.sort((a, b) => a - b);
let closest = Infinity;
let left = 0, right = rightSums.length - 1;
// Two pointer approach to find closest sum
while (left < leftSums.length && right >= 0) {
const currentSum = leftSums[left] + rightSums[right];
// Update closest if better
if (Math.abs(currentSum - target) < Math.abs(closest - target)) {
closest = currentSum;
}
// Move pointers based on comparison
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum; // Exact match
}
}
return closest;
}
console.log(closestSubsetSum([1, 3, 5, 7, 9], 15)); // 15
console.log(closestSubsetSum([1, 3, 5, 7, 9], 16)); // 15 or 16
Note: Two-pointer approach after sorting both halves is more efficient than nested iteration. The key insight: if current sum is less than target, increase left pointer; if greater, decrease right pointer.
4. 4Sum Problem Optimization
| Approach | Method | Advantage | Complexity |
|---|---|---|---|
| Brute Force 4Sum | Four nested loops to check all quadruplets | Simple to implement | O(n^4) |
| Hash Map 4Sum | Store all pair sums in hash map, look for complement pairs | Reduces to two-pair problem | O(n^2) avg |
| Meet in Middle | Generate all pair sums from first half and second half, find matching pairs | More memory efficient than hash map approach | O(n^2 log n) |
| Two Pointer 4Sum | Fix two elements, use two pointers for remaining two | No extra space, handles duplicates well | O(n^3) |
Example: 4Sum using Meet in the Middle
function fourSum(nums, target) {
const n = nums.length;
if (n < 4) return [];
nums.sort((a, b) => a - b);
const result = [];
// Generate all pair sums with indices
const pairSums = [];
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
pairSums.push({
sum: nums[i] + nums[j],
i: i,
j: j
});
}
}
// Sort by sum
pairSums.sort((a, b) => a.sum - b.sum);
// Two pointer to find matching pairs
let left = 0, right = pairSums.length - 1;
while (left < right) {
const currentSum = pairSums[left].sum +
pairSums[right].sum;
if (currentSum === target) {
// Check non-overlapping indices
const p1 = pairSums[left];
const p2 = pairSums[right];
if (p1.j < p2.i || p2.j < p1.i) {
const quad = [
nums[p1.i], nums[p1.j],
nums[p2.i], nums[p2.j]
].sort((a, b) => a - b);
// Check for duplicates
const key = quad.join(',');
if (!result.find(r =>
r.join(',') === key)) {
result.push(quad);
}
}
left++;
right--;
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
return result;
}Example: 4Sum using Two Pointers (Optimal)
function fourSumTwoPointer(nums, target) {
nums.sort((a, b) => a - b);
const n = nums.length;
const result = [];
for (let i = 0; i < n - 3; i++) {
// Skip duplicates for i
if (i > 0 && nums[i] === nums[i-1]) {
continue;
}
for (let j = i + 1; j < n - 2; j++) {
// Skip duplicates for j
if (j > i + 1 &&
nums[j] === nums[j-1]) {
continue;
}
let left = j + 1, right = n - 1;
while (left < right) {
const sum = nums[i] + nums[j] +
nums[left] + nums[right];
if (sum === target) {
result.push([
nums[i], nums[j],
nums[left], nums[right]
]);
// Skip duplicates
while (left < right &&
nums[left] === nums[left+1]) {
left++;
}
while (left < right &&
nums[right] === nums[right-1]) {
right--;
}
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
console.log(fourSumTwoPointer(
[1,0,-1,0,-2,2], 0
));
// [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]5. Exponential to Polynomial Time Reduction
| Problem Class | Original Complexity | After Meet in Middle | Key Insight |
|---|---|---|---|
| Subset Sum | O(2^n) brute force |
O(2^(n/2) × log 2^(n/2)) |
Split into two halves, combine with sorting/hashing |
| K-Sum Problem | O(n^k) nested loops |
O(n^(k/2) × log n) |
Split k elements into two groups of k/2 |
| Knapsack Variants | O(2^n) enumerate all subsets |
O(2^(n/2)) |
Generate half solutions, combine optimally |
| Partition Problem | O(2^n) all partitions |
O(2^(n/2)) |
Two halves generate sums, check if complement exists |
Example: Partition array into two subsets with minimum difference
function minimizeSubsetSumDifference(nums) {
const n = nums.length;
const totalSum = nums.reduce((a, b) => a + b, 0);
const mid = Math.floor(n / 2);
// Generate all subset sums from each half
function generateSums(start, end) {
const sums = [];
const size = end - start;
for (let mask = 0; mask < (1 << size); mask++) {
let sum = 0;
for (let i = 0; i < size; i++) {
if (mask & (1 << i)) {
sum += nums[start + i];
}
}
sums.push(sum);
}
return sums;
}
const leftSums = generateSums(0, mid);
const rightSums = generateSums(mid, n);
// Sort right sums for binary search
rightSums.sort((a, b) => a - b);
let minDiff = Infinity;
// For each left sum, find best right sum
for (const leftSum of leftSums) {
// We want leftSum + rightSum to be close to totalSum/2
const target = Math.floor(totalSum / 2) - leftSum;
// Binary search for closest value
let left = 0, right = rightSums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const subset1Sum = leftSum + rightSums[mid];
const subset2Sum = totalSum - subset1Sum;
const diff = Math.abs(subset1Sum - subset2Sum);
minDiff = Math.min(minDiff, diff);
if (rightSums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// Also check left boundary
if (left < rightSums.length) {
const subset1Sum = leftSum + rightSums[left];
const subset2Sum = totalSum - subset1Sum;
minDiff = Math.min(minDiff,
Math.abs(subset1Sum - subset2Sum));
}
}
return minDiff;
}
console.log(minimizeSubsetSumDifference([1, 6, 11, 5])); // 1
// Explanation: {1,5,6} = 12, {11} = 11, diff = 1
Note: Meet in the middle is most effective when:
- Problem has exponential complexity O(2^n) or O(n^k) where k is large
- Search space can be divided into independent halves
- Results from halves can be combined efficiently (sorting, hashing)
- n is typically between 20-40 (too small: regular approach works; too large: even 2^(n/2) is too big)
Example: Comparison of complexities
// Complexity comparison for n = 40:
// Brute force: O(2^40) = 1,099,511,627,776 operations (~1 trillion)
// Meet in middle: O(2^20 × log 2^20) = 1,048,576 × 20 = 20,971,520 operations (~21 million)
// Reduction factor: 2^40 / (2^20 × 20) ≈ 52,428 times faster!
// Space complexity:
// Brute force: O(1) (no extra space)
// Meet in middle: O(2^(n/2)) to store subset sums
// Trade-off: Exchange space for dramatic time improvement
function demonstrateReduction() {
const n = 40;
console.log("Array size:", n);
console.log("Brute force operations:", Math.pow(2, n));
console.log("Meet in middle operations:",
Math.pow(2, n/2) * (n/2));
console.log("Speed up factor:",
Math.pow(2, n) / (Math.pow(2, n/2) * (n/2)));
// For practical purposes:
// Brute force: days/weeks of computation
// Meet in middle: seconds
}Summary: Meet in the Middle Pattern
- Core Principle: Split search space in half, enumerate all possibilities in each half (O(2^(n/2)) each), combine results efficiently
- Complexity Reduction: O(2^n) → O(2^(n/2)), dramatic improvement for n > 20
- Two Array Sum: Generate sums from both halves, use hash map or binary search to find complementary sums
- Subset Sum: Enumerate all 2^(n/2) subset sums from each half, combine with sorting + two pointers or hash map
- Closest Sum: Sort both halves' sums, use two pointers to minimize |leftSum + rightSum - target|
- 4Sum Optimization: Generate all n^2 pair sums, find matching pairs using meet in middle or two pointers
- Space-Time Trade-off: Requires O(2^(n/2)) extra space to store subset sums, but achieves exponential time savings
- Typical Range: Most effective for 20 ≤ n ≤ 40 where brute force is impossible but 2^(n/2) is manageable
- Combination Methods: Hash map (O(1) lookup), sorted array + binary search (O(log n) lookup), two pointers (O(n) scan)
- Applications: Subset sum, knapsack variants, k-sum problems, partition problems, closest pair problems