Introduction to Meet in the Middle

Meet in the middle exploits the fact that 2^n is infeasible but 2^(n/2) is cheap: split the input into two halves, enumerate every combination of each half separately, then pair a result from the left half with a result from the right half using a sort + binary search (or two-pointer) instead of a second nested enumeration — turning an O(2^n) search into roughly O(2^(n/2) · n).

Recognize the pattern

• n is too big for O(2^n) brute force but small enough that 2^(n/2) is manageable — the classic tell is n between 30 and 45 (n ≤ 40 here; 2^40 ≈ 10^12 is too slow, 2^20 ≈ 10^6 is instant).
• The problem asks over all subsets, all partitions, or all ways to pick/exclude items (subset-sum, closest-to-target sum, k-subset partitioning, counting pairs of subsets with a XOR/sum property).
• There's a natural way to combine two independent partial results into a full answer (sum + sum, XOR + XOR) with an efficient combine step (binary search, hashing, two pointers).

Brute force → optimal

Brute force: enumerate all 2^n subsets of the full array, compute each sum, keep the best ≤ S. Cost: O(2^n) time, O(1) extra space (streaming). For n = 40 that's ~10^12 operations — infeasible in a few seconds.

Optimal (meet in the middle): split the n items into two halves of size n/2. Enumerate all 2^(n/2) subset sums of each half independently (this alone is exponentially cheaper — square-rooting the search space). Sort one half's sums, then for every sum in the other half binary-search for the best complementary value that keeps the total ≤ S.

Complexity, derived

Let h = n/2.

• Generating subset sums per half: a half of size h has 2^h subsets; enumerating them via recursion/bitmask visits each subset once, doing O(1)–O(h) work per subset (O(h) if you rebuild the sum from a bitmask, O(1) with incremental include/exclude recursion). Take the safe bound: O(2^h · h) per half, i.e. O(2^(n/2) · n) total for both halves combined (since h = n/2, the two halves' work sums, not multiplies).
• Sorting the right half's sums: 2^h values, so O(2^h log 2^h) = O(2^h · h) = O(2^(n/2) · n).
• Combine step: for each of the 2^h left sums, one binary search over 2^h sorted right sums costs O(h), giving O(2^h · h) = O(2^(n/2) · n) total.
• Overall time: O(2^(n/2) · n) — for n = 40, h = 20: 2^20 ≈ 10^6, times n = 40 ⇒ ~4×10^7 operations, trivially fast versus 2^40 ≈ 10^12.
• Space: storing both subset-sum lists is O(2^(n/2)) ≈ 10^6 longs for n = 40 (~8 MB) — fine.

Worked example

Array [3, 15, 14, 9, 6, 2], S = 10 (using the small S from the source so the trace is short). Split: left = [3, 15, 14], right = [9, 6, 2].

Sort right → [0, 2, 6, 8, 9, 11, 15, 17]. Now scan left sums that are ≤ S = 10 (only 0 and 3 qualify) and for each, binary-search the largest right value ≤ (S − left):

Best answer: 9 (e.g. subset {9} or {3, 6}), both ≤ S = 10 and no combination beats 9.

Java implementation

static List<Long> generateSubsetSums(int[] arr) {
    int m = arr.length;
    List<Long> sums = new ArrayList<>();
    for (int mask = 0; mask < (1 << m); mask++) {
        long s = 0;
        for (int i = 0; i < m; i++) if ((mask & (1 << i)) != 0) s += arr[i];
        sums.add(s);
    }
    return sums;
}

static long maxSubsetSumAtMostS(int[] nums, long S) {
    int n = nums.length, mid = n / 2;
    int[] left = Arrays.copyOfRange(nums, 0, mid);
    int[] right = Arrays.copyOfRange(nums, mid, n);
    List<Long> sumLeft = generateSubsetSums(left);
    List<Long> sumRight = generateSubsetSums(right);
    Collections.sort(sumRight);
    long best = 0;
    for (long sLeft : sumLeft) {
        if (sLeft > S) continue;
        long remaining = S - sLeft;
        // largest value in sumRight that is <= remaining
        int lo = 0, hi = sumRight.size() - 1, idx = -1;
        while (lo <= hi) {
            int m = (lo + hi) / 2;
            if (sumRight.get(m) <= remaining) { idx = m; lo = m + 1; }
            else hi = m - 1;
        }
        if (idx >= 0) best = Math.max(best, sLeft + sumRight.get(idx));
    }
    return best;
}

Pitfalls

• Off-by-one in the binary search: you need the largest right sum ≤ remaining, not < or an exact match — a plain Collections.binarySearch only finds exact matches and needs the insertion-point trick (-(ip)-1) to recover the correct floor.
• Overflow: with values up to 10^12 and n up to 40, sums can reach ~4×10^13 — use long, never int.
• Uneven split cost: splitting n=41 as 20/21 keeps both halves at ≤ 2^21; splitting badly (e.g. 5/36) throws away the whole benefit — always split as evenly as possible.
• Forgetting duplicate/empty subset: the empty subset (sum 0) is a valid candidate and must be included — dropping it can silently produce a wrong optimum when no non-empty subset fits under S.

When to use / when not — trade-offs

Use meet in the middle when n is roughly 30–45 (2^n infeasible, 2^(n/2) is not) and the problem decomposes into two independent halves whose results combine via a cheap operation (sum, XOR, pair-count). Compare with:

• Bitmask DP (subset DP): handles n up to ~20 directly with O(2^n · n) states but doesn't scale to n=40; meet in the middle trades a more intricate combine step for reaching double the n.
• Pure brute force (2^n): simpler code, correct for n ≤ ~22, but exponentially worse for n in the 30s–40s — meet in the middle is strictly better there at the cost of extra memory (O(2^(n/2))) and combine-step complexity.
• Greedy/DP on sum (subset-sum DP over S): when S itself is small (say ≤ 10^6), a bitset/boolean DP over S is simpler and often faster; meet in the middle wins specifically when S is too large to index into (as here, S ≤ 10^12) but n is small.

Takeaways

• Meet in the middle turns O(2^n) into O(2^(n/2) · n) by enumerating each half separately and combining with sort + binary search.
• The tell is n in the 30–45 range with an exponential brute force and a cheap pairwise combine.
• Always use long for sums, split as evenly as possible, and don't forget the empty subset.
• Generalize by storing more than the sum: keep (sum, cardinality) when the problem constrains subset size (e.g. equal-size partitions), or (sum, bitmask) when you must reconstruct which items were chosen. Negative values are fine — the sort still gives a total order for the binary-search combine.

Recall question

Why is the overall time complexity O(2^(n/2) · n) rather than O(2^(n/2)) alone, and where does the extra factor of n come from?

Pattern derived from the classic subset-sum-under-a-bound formulation; complexity analysis and Java implementation original to this page.