Meet in the Middle

Quick Revisit

• USE WHEN: Brute-force is O(2^n) or O(n!) but n ≤ 40—split in half to make it feasible
• INVARIANT: Every valid combination is a pair (left-half result, right-half result); enumerate halves independently, combine via sort + binary search
• TIME: O(2^(n/2) · log(2^(n/2))) | SPACE: O(2^(n/2))
• CLASSIC BUG: Forgetting to sort one half before binary-searching, or off-by-one in the split index (left gets ⌊n/2⌋, right gets the rest)
• PRACTICE: 01-ladder-1100-to-1400

Split the search space in half, enumerate both halves independently, then combine results—reduces $O(2^n)$ to $O(2^{n/2})$.

Difficulty: Intermediate | Prerequisites: Sorting, Binary Search

---

Contents

• Intuition
• C++ STL Reference
• Implementation
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Quick Reference & Insights
• Further Reading

---

Intuition

You have 40 integers and a target $T$. Find a subset whose sum is closest to $T$ without exceeding it.

Brute force enumerates every subset. There are $2^{40}\approx 1.1\times {10}^{12}$ of them—over 1,000 seconds at ${10}^9$ operations per second. There is no obvious pruning strategy, so brute force is dead on arrival.

The saving insight: split the array in half (20 + 20), enumerate all $2^{20}\approx {10}^6$ subset sums for each half independently, then for each sum from the first half binary search for the best complement in the second half.

Think of two detective teams each searching half a city and compiling their own list of findings, then comparing notes once at the end. Neither team needs to know what the other saw during its search—they only meet in the middle.

The analogy breaks down when the combination step is not a simple merge but requires more complex matching; in those cases the "compare notes" step gets harder, but the core idea of halving the exponent remains.

The Split at a Glance

Original problem: enumerate 2^40 subsets  -->  ~10^12 ops  -->  TLE
                  |
                  v
     +------------------------+------------------------+
     |  Left half (20 items)  |  Right half (20 items) |
     |  2^20 = ~10^6 subsets  |  2^20 = ~10^6 subsets  |
     +----------+-------------+-------------+----------+
                |                           |
                v                           v
           Sort left                  Iterate right
                |                           |
                +-------------+-------------+
                              |
                              v
                 Combine via sort + binary search
                 Total: ~2*10^6 + 10^6*20 = 2*10^7  -->  AC

Connection to the birthday paradox. Just as the birthday paradox shows that in a room of 23 people there's a 50% chance two share a birthday (because we're checking $(\genfrac{}{}{0ex}{}{23}{2})$ pairs, not 365 days), MITM works because matching $2^{n/2}$ items against $2^{n/2}$ items is far cheaper than enumerating all $2^n$ possibilities. In both cases the trick is that combining two moderate-sized sets produces a number of interactions vastly smaller than the full combinatorial space—the birthday paradox exploits $O(k^2)$ pair collisions from $k$ samples, while MITM exploits $O(2^{n/2}\log 2^{n/2})$ sorted lookups instead of $O(2^n)$ brute force.

How much does halving the exponent actually save?

┌──────────┬─────────────────────┬──────────────────────┬──────────────┐
│    n     │  Brute 2^n          │  MITM 2x2^(n/2)      │  Speed-up    │
├──────────┼─────────────────────┼──────────────────────┼──────────────┤
│   20     │  1,048,576  (10^6)  │      2,048  (2x10^3) │      ~512x   │
│   30     │  1.07x10^9          │     65,536  (6x10^4) │   ~16,384x   │
│   36     │  6.87x10^10         │    262,144  (3x10^5) │  ~262,144x   │
│   40     │  1.10x10^12         │  2,097,152  (2x10^6) │  ~524,288x   │
│   44     │  1.76x10^13         │  8,388,608  (8x10^6) │ ~2,097,152x  │
│   50     │  1.13x10^15         │ 67,108,864  (7x10^7) │ ~16,777,216x │
└──────────┴─────────────────────┴──────────────────────┴──────────────┘
  n=40 sweet spot: from ~10^12 ops (>1000 sec) to ~2x10^6 ops (<0.01 sec)

The key takeaway: for $n=40$, brute force needs $2^{40}\approx {10}^{12}$ operations (over 1,000 seconds at ${10}^9$ ops/sec), while MITM needs only $2\times 2^{20}\approx 2\times {10}^6$ enumerations plus $\sim 2\times {10}^7$ total work with the binary search step—comfortably under 1 second.

Visual Walkthrough

Array (n = 8): [3, 7, 2, 5, 8, 1, 4, 6], target $T=20$.

Split into left = [3, 7, 2, 5] and right = [8, 1, 4, 6].

Step 1—Enumerate left subset sums (2^4 = 16 values):

Subsets of [3,7,2,5]:
{}->0  {3}->3  {7}->7  {2}->2  {5}->5
{3,7}->10  {3,2}->5  {3,5}->8  {7,2}->9  {7,5}->12
{2,5}->7   {3,7,2}->12  {3,7,5}->15  {3,2,5}->10
{7,2,5}->14  {3,7,2,5}->17

left_sums (sorted): [0,2,3,5,5,7,7,8,9,10,10,12,12,14,15,17]

Step 2—Enumerate right subset sums (2^4 = 16 values):

Subsets of [8,1,4,6]:
{}->0  {8}->8  {1}->1  {4}->4  {6}->6
{8,1}->9   {8,4}->12  {8,6}->14  {1,4}->5  {1,6}->7
{4,6}->10  {8,1,4}->13  {8,1,6}->15  {8,4,6}->18
{1,4,6}->11  {8,1,4,6}->19

right_sums: [0,1,4,5,6,7,8,9,10,11,12,13,14,15,18,19]

Step 3—For each right sum r, binary search left_sums for largest value $\le T-r$:

r =  0  -->  search for <= 20  -->  best left = 17  -->  total = 17
r =  1  -->  search for <= 19  -->  best left = 17  -->  total = 18
r =  4  -->  search for <= 16  -->  best left = 15  -->  total = 19
r =  5  -->  search for <= 15  -->  best left = 15  -->  total = 20  <-- best!
r =  6  -->  search for <= 14  -->  best left = 14  -->  total = 20  <-- tied
...

Best subset sum $\le 20$ is 20 (e.g. left subset $\{3,7,5\}=15$, right subset $\{1,4\}=5$).

Merge step visual—how binary search finds the complement:

For each right sum $r$, we compute the budget $T-r$ and binary search the sorted left array for the largest value $\le$ budget.

left_sums (sorted):
  [0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, 12, 14, 15, 17]

── r = 5, budget = T - r = 20 - 5 = 15 ──────────────────────────

  Binary search: upper_bound(left, 15)
                                                         ub
  [0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, 12, 14, 15, |17]
                                                     ▲
                                                  prev(ub) = 15
  best_left = 15  ->  total = 15 + 5 = 20 OK  (optimal!)

── r = 8, budget = T - r = 20 - 8 = 12 ──────────────────────────

  Binary search: upper_bound(left, 12)
                                              ub
  [0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, |12, 14, 15, 17]
                                                            
  Wait -- there are duplicate 12s.  upper_bound points past the
  LAST 12, so prev(ub) gives us the rightmost 12.

                                          ub
  [0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, 12, |14, 15, 17]
                                             ▲
                                          prev(ub) = 12
  best_left = 12  ->  total = 12 + 8 = 20 OK

── r = 19, budget = T - r = 20 - 19 = 1 ─────────────────────────

  Binary search: upper_bound(left, 1)
      ub
  [0, |2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, 12, 14, 15, 17]
   ▲
  prev(ub) = 0
  best_left = 0  ->  total = 0 + 19 = 19

The two-pointer alternative: if we sort both halves we can walk a left pointer forward and a right pointer backward simultaneously, maintaining $l+r\le T$. This avoids $\log$ factors but requires both halves sorted.

Two-pointer scan (both halves sorted):

L sorted: [0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, 12, 14, 15, 17]
R sorted: [0, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 19]
           ↑l                                                    ↑r

Step 1:  l=0 (val 0), r=15 (val 19)   ->  0+19=19 <= 20  ->  best=19, l++
Step 2:  l=1 (val 2), r=15 (val 19)   ->  2+19=21 > 20  ->  r--
Step 3:  l=1 (val 2), r=14 (val 18)   ->  2+18=20 <= 20  ->  best=20, l++
Step 4:  l=2 (val 3), r=14 (val 18)   ->  3+18=21 > 20  ->  r--
...continues until l and r cross...

Total scans: O(|L| + |R|) = O(2^(n/2))  -- no log factor!

Combination Methods — Summary

Method A: Binary Search               Method B: Two Pointers
+---------------------+               +---------------------+
| L (sorted)          |               | L (sorted)     -->  |
| [0, 2, 5, 7, 10,15]|               | [0, 2, 5, 7, 10,15]|
+---------+-----------+               +---------+-----------+
          ^                                     ^
          | upper_bound(T - r)                  | advance -->
          |                                     |
+---------+-----------+               +---------+-----------+
| R (unsorted is OK)  |               | R (sorted)     <--  |
| iterate each r      |               | [1, 4, 6, 8, 13,19]|
+---------------------+               +---------------------+
                                                ^
                                                | <-- retreat

Time: O(|R| * log|L|)                 Time: O(|L| + |R|)
Sort only L needed.                   Both L and R must be sorted.
Use when R may be filtered.           Use when you want no log factor.

Step 4—Count operations:

Brute force: $2^8=256$ subsets to enumerate. Meet in the middle: $2^4+2^4=32$ enumerations + $16\times \log 16=64$ binary search steps = 96 operations.

For $n=40$: brute force $\approx {10}^{12}$, meet in the middle $\approx 2\times {10}^6+{10}^6\times 20\approx 2.2\times {10}^7$. Over $\mathrm{40,000}\times$ faster.

The Invariant

+------------------------------------------------------------------+
| INVARIANT: left_sums contains all 2^(n/2) possible subset sums   |
| of the first half, sorted in non-decreasing order.  For each     |
| right subset sum r, the best overall sum <= T is found by        |
| binary searching for T - r in left_sums.  The global answer is   |
| max over all r of (best_left + r) where best_left + r <= T.      |
+------------------------------------------------------------------+

Why maintained: we enumerate every subset of each half exhaustively, so no valid combination is missed. Sorting left_sums lets us find the optimal complement in $O(\log 2^{n/2})=O(n)$ per query.

Look at Step 3 above—when $r=5$, we search for $\le 15$ in left_sums and immediately land on 15 via binary search. That pair $(15,5)$ gives the exact target 20 without scanning the entire left list.

What the Code Won't Teach You

The structure of the combine step varies by problem. The left-half enumeration is always the same (enumerate all 2^(n/2) subsets, compute their aggregate). But the combine step—how you match left and right—changes depending on what the problem asks for. "Exactly target" uses equal_range; "at most target" uses upper_bound and steps back; "count pairs with sum in [lo, hi]" uses two binary searches. Recognizing which combine variant you need is the real skill.

  Combine variants:

  "Exactly T":     for l in L: count += upper_bound(R, T-l) - lower_bound(R, T-l)
                   +------+------+------+------+------+
              R:   |  2   |  5   |  5   |  8   | 12   |
                   +------+------+------+------+------+
                            ^^^^^
                         T-l = 5  --> count += 2

  "At most T":     for l in L: it = upper_bound(R, T-l) - 1
                   +------+------+------+------+------+
              R:   |  2   |  5   |  5   |  8   | 12   |
                   +------+------+------+------+------+
                                        ^
                         T-l = 7  --> best = 5, count all <= 7

  "Max sum <= T":  for l in L: ans = max(ans, l + *prev(upper_bound(R, T-l)))
                   +------+------+------+------+------+
              R:   |  2   |  5   |  5   |  8   | 12   |
                   +------+------+------+------+------+
                                  ^
                         T-l = 6  --> best R = 5, total = l + 5

Meet in the middle vs. two pointers for pair sums. For "count pairs with sum = target" in a single array, sort and use two pointers—$O(n\log n)$. For "count pairs (one from set A, one from set B) with sum = target" where each set is exponentially large ($2^{20}$ possible values each): enumerate both sides and combine. The "two exponential sets" structure is the MITM trigger; "one polynomial array" usually allows two pointers instead.

Time complexity isn't just $2^{n/2}$—include the combine. Full complexity: enumerate left ($2^{n/2}$) + enumerate right ($2^{n/2}$) + sort one side ($2^{n/2}\times n/2$) + search for each element ($2^{n/2}\times \log 2^{n/2}$). For $n=40$: about $5\times 2^{20}\times 20\approx {10}^8$—tight but feasible in 2 seconds. Don't neglect the sort and search overhead when estimating runtime.

With those subtleties clear, here is when to reach for meet in the middle during a contest.

When to Reach for This

Trigger phrases:

• "$n\le 40$" (too big for $2^n$, perfect for $2^{n/2}$)
• "subset sum", "subset XOR", "partition into two groups"
• "split in half" or "exponential but n is medium-sized"
• "find pair from two sets" where each set is generated by enumeration

Counter-examples:

• $n\le 20$—just enumerate all $2^n$ subsets directly, no need to split.
• $n>50$—even $2^{25}\approx 3.3\times {10}^7$ per half might be tight, and the combination step can blow up. Consider DP or other structural approaches.
• Problem has optimal substructure and overlapping subproblems—use DP (e.g., bounded knapsack with small weights).

Distinguishing feature: meet in the middle shines when $n$ sits in the "awkward middle" (roughly 25–45) where full enumeration is too slow but the halved enumeration fits comfortably.

---

C++ STL Reference

Function / Class	Header	What it does	Time
vector<long long>	<vector>	Store subset sums	--
sort(v.begin(), v.end())	<algorithm>	Sort left_sums for binary search	$O(m\log m)$
upper_bound(v.begin(), v.end(), x)	<algorithm>	Iterator to first element $>x$	$O(\log m)$
lower_bound(v.begin(), v.end(), x)	<algorithm>	Iterator to first element $\ge x$	$O(\log m)$
prev(it)	<iterator>	Move iterator back one position	$O(1)$
unique(v.begin(), v.end())	<algorithm>	Remove consecutive duplicates (optional dedup)	$O(m)$
merge(a.begin(), a.end(), b.begin(), b.end(), out)	<algorithm>	Merge two sorted ranges	$O(m_1+m_2)$
unordered_set<long long>	<unordered_set>	$O(1)$ average lookup (exact-match variant)	$O(1)$ avg
bitset<N>	<bitset>	Compact subset representation for reconstruction	--

Notes:

• upper_bound returns the first element strictly greater than x. To find the largest element $\le x$, check upper_bound(..., x) then step back with prev() (after verifying it is not begin()).
• For exact-sum problems (find subset summing to exactly $T$), an unordered_set can replace sorting + binary search, giving $O(1)$ average lookup at the cost of higher constant factor and memory.

---

Implementation

Classic problem: given $n\le 40$ integers and a target $T$, find the maximum subset sum that does not exceed $T$.

The pipeline below shows the data flow at a glance:

  MITM Pipeline:

  Input: a[0..n-1], target T
           |
           v
  +--------+---------+
  | SPLIT at n/2     |
  +--+----------+----+
     |          |
     v          v
  a[0..h-1]  a[h..n-1]
     |          |
     v          v
  +--------+ +--------+
  | Enum   | | Enum   |
  | 2^h    | | 2^(n-h)|
  | subsets | | subsets|
  +---+----+ +---+----+
      |          |
      v          v
    L[]        R[]
      |          |
      v          |
  +--------+     |
  | Sort L |     |
  +---+----+     |
      |          |
      v          v
  +-----------------------+
  | For each r in R:      |
  | binary search L for   |
  | best l with l+r <= T  |
  +-----------+-----------+
              |
              v
           answer

Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; long long T;
    cin >> n >> T;
    vector<long long> a(n);
    for(auto &x : a) cin >> x;

    int h = n / 2;
    auto gen = [&](int lo, int hi) {
        int sz = hi - lo;
        vector<long long> sums(1 << sz, 0);
        for(int mask = 0; mask < (1 << sz); mask++)
            for(int i = 0; i < sz; i++)
                if(mask >> i & 1) sums[mask] += a[lo + i];
        sort(sums.begin(), sums.end());
        return sums;
    };

    auto L = gen(0, h);
    auto R = gen(h, n);

    long long ans = -1;
    for(long long r : R){
        if(r > T) continue;
        auto it = upper_bound(L.begin(), L.end(), T - r);
        if(it != L.begin()){
            --it;
            ans = max(ans, *it + r);
        }
    }
    cout << ans << "\n";
}

Explained Version

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; long long T;
    cin >> n >> T;
    vector<long long> a(n);
    for(auto &x : a) cin >> x;

    int h = n / 2;  // split point: first half [0, h), second half [h, n)

    // Generate all 2^sz subset sums for a[lo..hi-1].
    // Uses bitmask enumeration: bit i set means include a[lo+i].
    auto gen = [&](int lo, int hi) -> vector<long long> {
        int sz = hi - lo;
        vector<long long> sums(1 << sz, 0);
        for(int mask = 0; mask < (1 << sz); mask++)
            for(int i = 0; i < sz; i++)
                if(mask >> i & 1)
                    sums[mask] += a[lo + i];
        // Sort so we can binary search later
        sort(sums.begin(), sums.end());
        return sums;
    };

    auto L = gen(0, h);   // all 2^h subset sums of left half
    auto R = gen(h, n);   // all 2^(n-h) subset sums of right half

    long long ans = -1;   // -1 means no valid subset found yet
    for(long long r : R){
        if(r > T) continue;  // right sum alone exceeds target, skip

        // We want the largest l in L such that l + r <= T,
        // i.e. l <= T - r.  upper_bound gives first l > T-r,
        // so we step back one to get the answer.
        auto it = upper_bound(L.begin(), L.end(), T - r);
        if(it != L.begin()){
            --it;
            ans = max(ans, *it + r);
        }
    }

    // ans == -1 only if every single element exceeds T and T >= 0
    // (empty subset has sum 0 which is always <= T when T >= 0)
    cout << ans << "\n";
}

---

Operations Reference

Each phase of the meet-in-the-middle pipeline has its own cost—the combine step often dominates.

Operation	Time	Space
Enumerate all subset sums of one half	$O(2^{n/2}\cdot n)$	$O(2^{n/2})$
Sort one half's subset sums	$O(2^{n/2}\cdot n)$	$O(1)$ extra
Binary search per right-half element	$O(\log 2^{n/2})=O(n)$	$O(1)$
Combine (iterate right, search left)	$O(2^{n/2}\cdot n)$	$O(1)$
Total	$O(2^{n/2}\cdot n)$	$O(2^{n/2})$

The $n$ factor inside enumeration comes from summing up to $n/2$ elements per subset. For $n=40$ the total is $\approx 2\times {10}^7$ operations—well within a 1-second time limit.

---

Problem Patterns & Tricks

Subset Sum ≤ Target (Closest Sum)

Given $n\le 40$ values and a target $T$, find the subset sum closest to $T$ (from below, above, or exactly equal). Split, enumerate, sort one half, binary search from the other. This is the canonical MITM problem—everything else in this section is a variation on this template.

Example problems:

• CF 888E -- Maximum Subsequence (~1800)
• CSES -- Meet in the Middle (classic)

Exact Subset Sum / Count

Count (or determine existence of) subsets summing to exactly $T$. Instead of binary search, use a hash map or lower_bound for exact match. When counting, sort left sums and, for each right sum $r$, count occurrences of $T-r$ via equal_range.

Worked example—counting with duplicates:

Array (n=6): [2, 3, 5, 2, 3, 5], target $T=10$. Split: left = [2, 3, 5], right = [2, 3, 5].

  Left subset sums:           Right subset sums:
  {} -> 0                     {} -> 0
  {2} -> 2                    {2} -> 2
  {3} -> 3                    {3} -> 3
  {5} -> 5                    {5} -> 5
  {2,3} -> 5                  {2,3} -> 5
  {2,5} -> 7                  {2,5} -> 7
  {3,5} -> 8                  {3,5} -> 8
  {2,3,5} -> 10               {2,3,5} -> 10

  L sorted: [0, 2, 3, 5, 5, 7, 8, 10]
  R sorted: [0, 2, 3, 5, 5, 7, 8, 10]
                         ^^^^
                    NOTE: 5 appears TWICE (from {5} and {2,3})

  Counting pairs with L + R = 10:
  r=0:  need L=10, count of 10 in L = 1  --> +1
  r=2:  need L=8,  count of 8 in L = 1   --> +1
  r=3:  need L=7,  count of 7 in L = 1   --> +1
  r=5:  need L=5,  count of 5 in L = 2   --> +2  <-- duplicates!
  r=5:  need L=5,  count of 5 in L = 2   --> +2  <-- again!
  r=7:  need L=3,  count of 3 in L = 1   --> +1
  r=8:  need L=2,  count of 2 in L = 1   --> +1
  r=10: need L=0,  count of 0 in L = 1   --> +1
                                    Total: 10 subsets sum to 10

  DO NOT deduplicate L! The two 5s represent DIFFERENT subsets.

// counting exact matches
sort(L.begin(), L.end());
long long cnt = 0;
for(long long r : R){
    auto [lo, hi] = equal_range(L.begin(), L.end(), T - r);
    cnt += hi - lo;
}

Example problems:

• CSES -- Meet in the Middle

Subset XOR

Replace addition with XOR and enumerate XOR-sums of each half. For "maximum XOR $\le T$" the combination step may require a trie instead of binary search (XOR doesn't preserve order); for "XOR equals $T$" a hash set works directly.

Example problems:

• CF 1006F -- Xor-Paths (~2100)

Bidirectional BFS / Search

MITM generalizes far beyond subsets. In shortest-path or state-space search, expand from both the start and the goal simultaneously and stop when the two frontiers collide. The search space shrinks from $O(b^d)$ to $O(b^{d/2})$, where $b$ is the branching factor and $d$ is the depth.

Example problems:

• CF 1395D -- Tim and His Painting (~2200)

4-Sum / k-Sum via Split

Given an array, find four elements summing to $T$. Compute all pairwise sums (two from each half of the positions), sort one list, binary search from the other. This drops the naive $O(n^4)$ cost to $O(n^2\log n)$.

// 4-sum via meet in the middle on pairs
vector<long long> pair_sums;
for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)
        pair_sums.push_back(a[i] + a[j]);
sort(pair_sums.begin(), pair_sums.end());
// For each pair sum p, binary search for T - p

Example problems:

• CF 1500A -- Going Home (~2000)

Multi-Constraint Meet in the Middle

When each element has two attributes (e.g., weight and value), enumerate (weight, value) pairs for each half. Sort the left pairs by weight, build a prefix-maximum array on values, then for each right pair $(w_r,v_r)$ binary search for the largest weight $\le W-w_r$ and read the prefix-max value.

Example problems:

• CF 888E -- Maximum Subsequence (~1800)

String Meet in the Middle

MITM applies to string problems where the search space is over rearrangements or character selections. Split the string in half, enumerate properties of all configurations of each half, then match the halves that combine into a valid answer.

Motivating problem: Given a string $s$ of length $n\le 40$ consisting of lowercase letters, determine whether any rearrangement of the first half concatenated with any rearrangement of the second half can form a palindrome.

A string is a palindrome if the character at position $i$ equals the character at position $n-1-i$. Rather than checking all $(20!{)}^2$ rearrangements (impossible), we observe:

• A string of length $n$ is a palindrome iff at most one character has odd frequency (for odd $n$), or all characters have even frequency (even $n$).
• Split $s$ into left half $s[0..h)$ and right half $s[h..n)$.
• For each half, enumerate all $2^h$ subsets of "which characters from this half go to even-indexed positions." For each subset, compute a signature: a frequency vector (or hash) representing the character surplus/deficit that the other half must compensate.
• Store left signatures in a hash set. For each right signature, check if the complementary signature exists in the set.

// Sketch: string palindrome via MITM
// Encode character balance as a bitmask (odd/even parity per character)
unordered_set<int> left_parities;
for(int mask = 0; mask < (1 << h); mask++){
    int parity = 0;
    for(int i = 0; i < h; i++)
        if(mask >> i & 1)
            parity ^= (1 << (s[i] - 'a'));  // toggle parity of char
    left_parities.insert(parity);
}
// For the full string to be a palindrome, combined parity must be 0
// (even length) or a single bit (odd length)
for(int mask = 0; mask < (1 << (n - h)); mask++){
    int parity = 0;
    for(int i = 0; i < n - h; i++)
        if(mask >> i & 1)
            parity ^= (1 << (s[h + i] - 'a'));
    // Need left_parity XOR parity == 0 or single bit
    if(left_parities.count(parity)) return true;       // even length case
    for(int c = 0; c < 26; c++)
        if(left_parities.count(parity ^ (1 << c))) return true; // odd length
}

More generally, string MITM works whenever you can decompose a string property into independent contributions from two halves and express the matching condition as a lookup (hash set, sorted search, etc.).

Example problems:

• CF 525E -- Anya and Cubes (~2000)—characters replaced by numbers with factorial option
• AtCoder ABC 184F -- Programming Contest—adaptable to string variants

---

Contest Cheat Sheet

+--------------------------------------------------------------+
| MEET IN THE MIDDLE  --  CHEAT SHEET                          |
+--------------------------------------------------------------+
| WHEN TO USE:                                                 |
|   - n <= 40, brute force 2^n too slow                        |
|   - Subset sum / XOR / partition into two groups              |
|   - 4-sum or k-sum where pairwise split helps                |
|   - Bidirectional BFS on large state spaces                  |
+--------------------------------------------------------------+
| CORE PATTERN:                                                |
|   int h = n/2;                                               |
|   auto L = enumerate(0, h);   // 2^h sums                   |
|   auto R = enumerate(h, n);   // 2^(n-h) sums               |
|   sort(L);                                                   |
|   for(r : R) ans = max(ans, *prev(upper_bound(L, T-r)) + r);|
+--------------------------------------------------------------+
| COMPLEXITY:  Time  O(2^(n/2) * n)                            |
|              Space O(2^(n/2))                                 |
+--------------------------------------------------------------+
| WATCH OUT:                                                   |
|   - Use long long (sums overflow int for n=40)               |
|   - upper_bound returns begin() if no valid element          |
|   - Check r <= T before searching (skip invalid rights)      |
|   - Split evenly: floor(n/2) vs ceil(n/2) differ by 1       |
|   - Empty subset (sum=0) is valid -- don't forget it         |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Integer Overflow

With 40 values each up to ${10}^9$, the maximum subset sum is $40\times {10}^9=4\times {10}^{10}$—nearly 20× the int maximum of $\approx 2.1\times {10}^9$. Always use long long for sums and the target.

  Overflow danger zone:

  n = 40, each a[i] up to 10^9
  Max subset sum = 40 * 10^9 = 4 * 10^10

  int range:      [-2.1 * 10^9  ...  2.1 * 10^9]
                                         ^
                                    4*10^10 OVERFLOWS!

  long long range: [-9.2 * 10^18 ... 9.2 * 10^18]
                                         ^
                                    4*10^10 fits easily

  +---------------------------------------------+
  | RULE: If n > 20 or values > 10^4, use       |
  |       long long for ALL accumulated values.  |
  +---------------------------------------------+

Off-by-One in upper_bound

upper_bound(L.begin(), L.end(), T - r) returns an iterator to the first element strictly greater than T - r. Decrement it to get the largest value $\le T-r$. But when it == L.begin(), no left sum is small enough—do not decrement past begin().

auto it = upper_bound(L.begin(), L.end(), T - r);
if(it == L.begin()) continue;  // no left sum small enough
--it;

Uneven Split

When $n$ is odd the two halves differ by 1. This is fine—one half has $2^{\lfloor n/2\rfloor }$ sums, the other $2^{\lceil n/2\rceil }$. Both are $O(2^{n/2})$. Just make sure your loop bounds are [0, h) and [h, n) where h = n / 2.

Forgetting the Empty Subset

The empty subset has sum 0 and is always valid. Starting bitmask enumeration at mask = 1 silently drops it—always start at mask = 0.

  Bitmask enumeration for [a, b, c]:

  mask = 0:  000 --> {}     --> sum = 0     <-- DON'T SKIP THIS!
  mask = 1:  001 --> {a}    --> sum = a
  mask = 2:  010 --> {b}    --> sum = b
  mask = 3:  011 --> {a,b}  --> sum = a+b
  mask = 4:  100 --> {c}    --> sum = c
  mask = 5:  101 --> {a,c}  --> sum = a+c
  mask = 6:  110 --> {b,c}  --> sum = b+c
  mask = 7:  111 --> {a,b,c}--> sum = a+b+c

  If target T = 0, the empty subset is the ONLY answer.
  Starting at mask = 1 misses it --> Wrong Answer!

Duplicate Sums Inflating Count

When counting exact matches, duplicate values in left_sums are features, not bugs—they represent different subsets that happen to share a sum. Do not deduplicate unless the problem asks for distinct sums.

Debugging Tips

• Print both halves' sorted sums and eyeball them for sanity.
• For small $n$ ($\le 20$), run brute-force alongside meet-in-the-middle and compare answers on random inputs.
• If the answer is off by a small amount, check whether you handle the empty subset and the full subset of each half.
• Verify that the split point h = n / 2 is consistent between enumeration and the main loop.

Mental Traps

Trap 1: "n ≤ 40, I'll use bitmask DP."

Bitmask DP on 40 elements needs $2^{40}\approx {10}^{12}$ states—over 1,000 seconds. The $n\le 40$ constraint is precisely the range where bitmask DP collapses and meet-in-the-middle becomes the right tool.

  WRONG thinking:                       RIGHT thinking:
  +---------------------------+         +---------------------------+
  | n <= 40? Bitmask DP!      |         | n <= 40? Check the range! |
  |                           |         |                           |
  | dp[mask] for all 2^40     |         | n <= 20: bitmask DP OK   |
  | masks...                  |         | 21 <= n <= 45: MITM       |
  |                           |         | n > 45: need other ideas  |
  | 2^40 = 10^12 states       |         |                           |
  |   --> TLE!                |         | 2^20 = 10^6 per half     |
  +---------------------------+         | --> ~10^7 total, fast!    |
                                        +---------------------------+

Trap 2: "I need to enumerate all 2^40 subsets anyway."

The insight is that you don't. You enumerate $2^{20}$ subsets of each half, then combine. The total work is $O(2^{20}\times \log 2^{20})\approx 2\times {10}^7$.

  WRONG:                                RIGHT:
  +---------------------------+         +---------------------------+
  | Enumerate ALL subsets:    |         | Enumerate HALF + HALF:    |
  |                           |         |                           |
  | {}, {a1}, {a2}, ...      |         | Left half:  2^20 subsets  |
  | {a1,a2,...,a40}           |         | Right half: 2^20 subsets  |
  |                           |         |                           |
  | Total: 2^40 = 10^12      |         | Combine: binary search    |
  |        +---------+        |         |                           |
  |        |  TLE!   |        |         | Total: 2 * 10^6 + 2*10^7 |
  |        +---------+        |         |        +--------+         |
  +---------------------------+         |        |  AC!   |         |
                                        |        +--------+         |
                                        +---------------------------+

Trap 3: "Meet in the middle is just binary search."

Binary search is one possible combine step, not the whole technique. The "split, enumerate, combine" structure appears in cryptographic attacks, spatial queries, and any domain where full enumeration is $2^n$ but half-enumeration is $2^{n/2}$. The combine step can be a hash lookup, a trie walk, or two pointers—binary search is just the most common choice.

  MITM structure:
  +------------------+     +------------------+     +-----------+
  | Enumerate left   |     | Enumerate right  |     | Combine   |
  | 2^(n/2) values   |     | 2^(n/2) values   |     | via sort  |
  |                  |     |                  |     | + search  |
  +--------+---------+     +--------+---------+     +-----+-----+
           |                        |                      |
           v                        v                      v
      Binary search is         Enumeration is         The REAL trick
      only HERE -----+         the heavy work         is splitting the
                     |                                 exponent in half
                     v
              (combine step)

---

Self-Test

• [ ] State the constraint range where meet in the middle applies (what n is too small for MITM? What n is too large?).
• [ ] Write the skeleton of a meet-in-the-middle solution: enumerate both halves, sort one, combine—with the correct upper_bound - lower_bound count for "exactly target."
• [ ] Explain why the time complexity is O(2^(n/2) x n), not O(2^n), and compute the approximate number of operations for n = 40.
• [ ] Describe the combine step for "find the maximum subset sum that is <= target"—which binary search variant do you use?
• [ ] Name one problem where meet in the middle applies that is not a subset sum problem.
• [ ] Explain why you must NOT deduplicate left_sums when counting exact matches.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Meet in the Middle	CSES	Easy	Exact subset sum count, canonical template
2	Maximum Subsequence	CF 888E	Medium	Max subset sum $\le T$, direct application
3	Xor-Paths	CF 1006F	Medium	Meet in the middle on grid paths with XOR
4	Closest Subset Sum	AtCoder ABC184F	Medium	Subset sum closest to $T$, three-way split trick
5	Going Home	CF 1500A	Medium	4-sum variant via pairwise enumeration
6	Reachable Numbers	CF 1157E	Medium	Bidirectional search in state space
7	Little Elephant and Subset Sums	CodeChef	Hard	Multi-constraint enumeration
8	Number of Subsequences	CF Gym	Hard	Counting with meet in the middle + hashing

---

Quick Reference & Insights

The Aha Moment

When $n\approx 40$, you can't enumerate $2^n$, but you CAN enumerate $2^{20}$ twice and combine. That single split turns 1000 seconds into 0.01 seconds.

If I Had 5 Minutes

1. Split the array at n/2.
2. Enumerate all $2^{n/2}$ subset sums for each half.
3. Sort the left half's sums.
4. Search for each right sum's complement via upper_bound.
5. Track the global best across all left-right pairs.

Real-Life Analogy

Cracking a 10-digit combination lock by trying all ${10}^{10}$ combos is hopeless—but split it into two 5-digit halves, try ${10}^5$ each, and match in the middle.

Pattern Fingerprint

Constraint you see	Technique to reach for	Why
$n\le 20$	Bitmask enumeration / bitmask DP (bit-manipulation)	$2^{20}\approx {10}^6$ fits directly
$21\le n\le 45$	Meet in the middle	$2^{n/2}$ fits; $2^n$ does not
$n\le {10}^3$, weights $\le {10}^5$	Knapsack DP (dp-knapsack)	Pseudo-polynomial DP is faster
Large state space, known start+goal	Bidirectional BFS	Halve the depth, square-root the states
Array pair sums, polynomial $n$	Two pointers	$O(n\log n)$ beats enumeration

Complexity Quick-Reference (with combine cost)

| n  | Brute 2^n  | MITM 2^(n/2)*n  | Speedup     |
|----|------------|-----------------|-------------|
| 20 | 10^6       | 2*10^4          | 50x         |
| 30 | 10^9       | 5*10^5          | 2000x       |
| 40 | 10^12      | 2*10^7          | 50000x      |
| 50 | 10^15      | 8*10^8          | 1200000x    |

Rating Progression (Codeforces)

+--------------------------------------------------------------+
| CF ~1200  Know that MITM exists; recognize "n <= 40" as a    |
|           signal. Solve CSES Meet in the Middle.              |
+--------------------------------------------------------------+
| CF ~1500  Implement the full template from scratch: enum,     |
|           sort, binary search. Handle long long and edge      |
|           cases (empty subset, all-negative values).          |
+--------------------------------------------------------------+
| CF ~1800  Apply MITM to non-obvious settings: XOR-paths on   |
|           grids (CF 1006F), 4-sum via pairwise enumeration,   |
|           multi-constraint problems with prefix-max trick.    |
+--------------------------------------------------------------+
| CF ~2100  Combine MITM with advanced structures: tries for    |
|           XOR queries, bidirectional BFS on large state       |
|           spaces, three-way splits for tighter bounds.        |
+--------------------------------------------------------------+

Before You Code — Checklist

1. Confirm $n$ is in the MITM sweet spot (roughly 25–45). Too small → brute force. Too large → need DP or structural insight.
2. Identify the aggregation operation (sum, XOR, product) and how the combine step works (binary search, hash set, trie).
3. Choose long long if values can exceed $2\times {10}^9$ in any accumulated sum.
4. Decide sort+binary search vs. two pointers vs. hash map for the combine step.
5. Plan subset reconstruction if the problem asks which elements, not just the value (store bitmasks alongside sums).

What Would You Do If...?

Scenario 1: "n = 36, find subset with XOR closest to T." Split into two halves of 18. Enumerate XOR-sums of each half. For "closest XOR to T", you can't just binary search—XOR doesn't preserve order. Build a trie of left XOR-sums, then for each right XOR-sum $r$, greedily walk the trie to maximize/minimize $l\oplus r\oplus T$. See bit-manipulation for trie-based XOR techniques.

Scenario 2: "n = 40, count subsets with sum in range [A, B]." Split and enumerate both halves. Sort left sums. For each right sum $r$, count left sums $l$ where $A-r\le l\le B-r$ using two binary searches: upper_bound(L, B-r) - lower_bound(L, A-r).

Scenario 3: "n = 40, each item has weight and value. Maximize value with weight $\le W$." This is multi-constraint MITM. Enumerate (weight, value) pairs for each half. Sort left pairs by weight. Build a prefix-maximum array on values (after sorting by weight). For each right pair $(w_r,v_r)$, binary search for the largest weight $\le W-w_r$ in the left array, then read the prefix-max value.

Historical Note

The meet-in-the-middle idea dates to the baby-step giant-step algorithm (Daniel Shanks, 1971) for computing discrete logarithms in group theory. It later appeared in cryptanalysis of double DES encryption (Diffie and Hellman, 1977)—an attacker splits the key space in half and matches precomputed tables from both sides, reducing a $2^{112}$ brute-force search to $2^{56}$ time and space. In competitive programming it became a staple for subset-sum variants where $n$ sits in the 25–45 range.

The Mistake That Teaches

"I coded MITM for n=40, but it ran in 8 seconds instead of under 1..."

The bug: inside the enumeration loop, the contestant recomputed the subset sum from scratch for every mask—iterating over all $n/2$ bits each time.

// SLOW: recomputes from scratch for each mask
for(int mask = 0; mask < (1 << h); mask++){
    long long s = 0;
    for(int i = 0; i < h; i++)
        if(mask >> i & 1) s += a[i];
    sums[mask] = s;
}

The fix: use the incremental trick. Each mask differs from mask ^ (mask & -mask) by exactly one bit:

// FAST: O(1) per mask using incremental computation
sums[0] = 0;
for(int mask = 1; mask < (1 << h); mask++){
    int lowbit = mask & (-mask);
    int idx = __builtin_ctz(lowbit);
    sums[mask] = sums[mask ^ lowbit] + a[idx];
}

Both are $O(2^h\cdot h)$ in theory, but the incremental version has a much smaller constant. For $h=20$, the difference is ~20x in practice.

Mnemonic Anchor

"Split the exponent, merge the answer."—If you remember one sentence about meet in the middle, let it be this one.

When NOT to Use This

• $n\le 20$: Just enumerate $2^n$ directly. MITM adds code complexity for no speed gain. See complete-search.
• $n>50$: Even $2^{25}\approx 3.3\times {10}^7$ per half is tight, and the combine step's $O(2^{25}\times 25)$ overhead may TLE. Look for polynomial-time DP or structural observations.
• Problem has optimal substructure: If weights are small enough for knapsack DP ($O(n\times W)$ with $W\le {10}^6$), DP is simpler and faster. See dp-knapsack.
• Single array, polynomial size: If you need "two elements from one array summing to T", use sorting + two pointers at $O(n\log n)$, not MITM.
• Problem requires listing all valid subsets: MITM finds the best aggregate or a count, but doesn't efficiently enumerate every valid subset.

Debug This!

Find the bug in each snippet. Answers are in the collapsed section below.

Bug 1—The Silent Overflow:

int n; int T;
cin >> n >> T;
vector<int> a(n);
for(auto &x : a) cin >> x;
// ... rest of MITM with int sums ...

Bug 2—The Off-by-One:

for(long long r : R){
    auto it = upper_bound(L.begin(), L.end(), T - r);
    --it;
    ans = max(ans, *it + r);
}

Bug 3—The Missing Subsets:

auto gen = [&](int lo, int hi) {
    int sz = hi - lo;
    vector<long long> sums;
    for(int mask = 1; mask < (1 << sz); mask++){
        long long s = 0;
        for(int i = 0; i < sz; i++)
            if(mask >> i & 1) s += a[lo + i];
        sums.push_back(s);
    }
    sort(sums.begin(), sums.end());
    return sums;
};

Bug 4—The Wrong Split:

int h = n / 2;
auto L = gen(0, h);
auto R = gen(h, h + n/2);

Bug Answers

1. T and sums are int. For $n=40$ with values up to ${10}^9$, sums reach $4\times {10}^{10}$—overflow. Use long long for T, a, and all sums.
2. No check for it == L.begin(). If all left sums exceed T - r, decrementing begin() is undefined behavior. Add if(it == L.begin()) continue; before the decrement.
3. Loop starts at mask = 1, skipping mask = 0 (the empty subset with sum 0). If $T=0$, this misses the only valid answer. Start at mask = 0.
4. Right half uses gen(h, h + n/2) instead of gen(h, n). When $n$ is odd (e.g. $n=41$, $h=20$), this covers indices 20-39 but misses index 40, silently losing one element.

---

Further Reading

• cp-algorithms.com—Meet in the Middle—concise writeup with complexity analysis and code
• USACO Guide—Meet in the Middle—curated problem set with difficulty ratings
• CF Blog—Meet in the Middle Tutorial—community tutorial with advanced variants
• For bidirectional BFS applications: see graph search techniques in ../03-graph-algorithms/