Meet in the Middle

1. Two Array Sum Combination

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)); // false

2. Subset Sum 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 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 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

Related Cheatsheets

Datastructures-algorithms