Chapter 86

Home

Meet in the Middle

When brute force is O(2ᴺ) and N ≤ 40, split the input in half. Enumerate all possibilities for each half (2^(N/2)), then combine results. Goes from impossible to feasible.

The Pattern: Subset Sum

Given N numbers, count subsets that sum to exactly T. Naive: 2ᴺ. Meet-in-the-middle: split N into halves of ~N/2, enumerate each (2^(N/2)), sort one half, binary search for complements.

C++ — meet in the middle for subset sum

vector gen_sums(vector& nums, int start, int end) {
    vector sums;
    int len = end - start;
    for (int mask = 0; mask < (1 << len); mask++) {
        long long sum = 0;
        for (int i = 0; i < len; i++)
            if (mask & (1 << i)) sum += nums[start + i];
        sums.push_back(sum);
    }
    return sums;
}

long long count_subsets(vector& nums, long long T) {
    int n = nums.size();
    int mid = n / 2;

    auto left = gen_sums(nums, 0, mid);
    auto right = gen_sums(nums, mid, n);
    sort(right.begin(), right.end());

    long long ans = 0;
    for (long long s : left) {
        // Count right sums that exactly match T - s
        auto [lo, hi] = equal_range(right.begin(), right.end(), T - s);
        ans += hi - lo;
    }
    return ans;
}

// N=40: 2^20 + 2^20 ≈ 2M — feasible!
// Naive 2^40 ≈ 10^12 — impossible

💡 N ≤ 40 is the sweet spot

For N ≤ 20, just brute force (2²⁰ = 1M). For N = 30-40, meet-in-the-middle (2¹⁵ + 2¹⁵ ≈ 65K each). For N ≥ 50, you need a different approach entirely.

Key Takeaways