Meet in the middle - DSA Learning Guide

Overview

Meet in the middle splits a brute-force search into two halves, enumerates all possibilities for each half independently, and then combines them. Instead of 2^n subsets, you enumerate 2^(n/2) for each half, which turns 2^40 (about 10^12, infeasible) into 2 x 2^20 (about 2 million, instant).

The combine step is usually sorting one half and binary searching (or two-pointer scanning) for the best partner from the other half. It applies when n is too big for plain 2^n (n around 30 to 40) but values are too big for DP over sums.

Digging a tunnel from both sides

Two crews start at opposite ends of a mountain and meet in the middle. Each only digs half the distance, finishing far sooner than one crew digging the whole tunnel.

When to use it

n is about 30 to 40, too large for 2^n but small enough for 2^(n/2).
Subset-sum style problems with large values, so DP over sums is impossible.
Problems that combine two independent choices (pairs of half-solutions).
Bidirectional search in large state spaces.

Problem patterns it solves

Subset sum closest to a goal

Recognize it when: n <= 40 and large values.

1755. Closest Subsequence Sum
2035. Partition Array Into Two Arrays to Minimize Sum Difference

Count pairs of half-solutions

Recognize it when: combine sums from two groups (4Sum counting).

454. 4Sum II
18. 4Sum

Bidirectional search

Recognize it when: search from start and goal and meet in the middle.

127. Word Ladder (bidirectional BFS)
752. Open the Lock (bidirectional)

Where it is used in real software

Cryptanalysis

The meet-in-the-middle attack is why double DES is barely stronger than single DES: an attacker encrypts from one side and decrypts from the other and matches in the middle.

Route planning

Bidirectional search in navigation explores from the origin and destination simultaneously to cut the explored area.

Puzzle solvers

Solving Rubik's cube-like puzzles by searching from the scrambled and solved states until they meet.

Key terms

Split: Divide the items into two halves A and B.
Enumerate: Compute all subset sums (or states) of each half: 2^(n/2) each.
Combine: For each value in A, find the best partner in sorted B.
Bidirectional BFS: Two BFS frontiers expanding toward each other.

How it works, step by step

1
Split the array in two halves
left = nums[0..n/2), right = nums[n/2..n).
2
Enumerate all subset sums of each half
Iteratively or with recursion; 2^(n/2) sums each.
3
Sort one half's sums
O(2^(n/2) x n/2).
4
For each sum in the other half, binary search
Find the partner that brings the total closest to the goal.
5
Track the best combined answer
Update the minimum difference as you go.

Closest subsequence sum, goal = 6

nums = [5, -7, 3, 5]; halves [5, -7] and [3, 5]

Left sum	Need from right	Closest right sum	Total	\|Total - goal\|
0	6	5 or 8	5 or 8	1 or 2
5	1	0	5	1
-7	13	8	1	5
-2	8	8	6	0

Right sums sorted: [0, 3, 5, 8]. Left sum -2 (5 + -7) with right sum 8 (3 + 5) reaches exactly 6. Total work: 4 + 4 sums instead of 16 subsets, a gap that becomes enormous at n = 40.

Implementation

1function subsetSums(arr) {2  let sums = [0];3  for (const x of arr) sums = sums.concat(sums.map((s) => s + x)); // doubles each time4  return sums;5}6 7// 1755. Closest Subsequence Sum8function minAbsDifference(nums, goal) {9  const half = nums.length >> 1;10  const left = subsetSums(nums.slice(0, half));11  const right = subsetSums(nums.slice(half)).sort((a, b) => a - b);12  let best = Infinity;13  for (const s of left) {14    const need = goal - s;15    let lo = 0, hi = right.length - 1;16    while (lo <= hi) { // closest value to need17      const mid = (lo + hi) >> 1;18      const total = s + right[mid];19      best = Math.min(best, Math.abs(total - goal));20      if (right[mid] < need) lo = mid + 1;21      else if (right[mid] > need) hi = mid - 1;22      else return 0;23    }24  }25  return best;26}27 28// 454. 4Sum II: pair sums of A+B, then look up -(C+D)29function fourSumCount(a, b, c, d) {30  const counts = new Map();31  for (const x of a) for (const y of b) counts.set(x + y, (counts.get(x + y) ?? 0) + 1);32  let total = 0;33  for (const x of c) for (const y of d) total += counts.get(-(x + y)) ?? 0;34  return total;35}

Complexity and performance

Brute forceO(2^n)

Infeasible past n ~ 25.

Meet in the middleO(2^(n/2) x n)

Enumeration plus sorting / binary search.

SpaceO(2^(n/2))

Stores one half's sums.

Bidirectional BFSO(b^(d/2))

vs O(b^d) for one-sided BFS.

Trade-offs

Time vs memory

You trade a square-root reduction in time for storing 2^(n/2) values; at n = 40 that is about a million numbers per half.

vs DP over sums

If values are small (sum up to about 10^5), subset-sum DP is simpler. Meet in the middle wins when values are huge.

Variants and related techniques

Two-pointer combine

Sort both halves and scan from opposite ends instead of binary searching.

Grouping by count

For equal-size partitions (2035), group subset sums by how many elements were chosen.

Hash-based combine

For exact targets, store one half in a hash map and look up complements.

Common mistakes

Using meet in the middle when n is small.
Fix: For n <= 20, plain enumeration is simpler.
Forgetting the empty subset.
Fix: Both halves must include sum 0 so solutions using only one half are considered.
Bidirectional BFS expanding the larger side.
Fix: Always expand the smaller frontier to minimize work.

Interview questions

Why does splitting in half help so much?

2^n = 2^(n/2) x 2^(n/2). Enumerating each half separately costs 2 x 2^(n/2), and a sorted combine adds only a logarithmic factor, so the exponent is halved.

When is meet in the middle the right tool?

When constraints show n around 30 to 40 with large values, which rules out both 2^n brute force and DP over values.

Practice problems

Problem	Difficulty	What it trains
454. 4Sum II	Medium	Pair sums in a map.
127. Word Ladder	Hard	Bidirectional BFS.
1755. Closest Subsequence Sum	Hard	Halves + binary search.
2035. Partition Array Into Two Arrays to Minimize Sum Difference	Hard	Group sums by size.