Skip to content
Tutorials Center
My learning

Topics

Lesson 68 of 225 ยท Recursion and Backtracking

Meet in the Middle and Branch and Bound

Cut exponential searches down with meet in the middle (subset sum in 2^(n/2)) and branch and bound (knapsack and a tiny travelling salesman), with Python code and counts.

Some problems have no known polynomial algorithm. Subset sum, the 0/1 knapsack in its raw form and the travelling salesman problem all seem to require looking at an exponential number of candidates. But "exponential" is not one size. A search over 2^40 candidates is hopeless, while a search over 2^20 takes a blink. Two classic techniques shrink an exponential search without changing the problem:

  • Meet in the middle splits the input in two halves, solves each half separately (2 x 2^(n/2) work instead of 2^n) and then combines the halves cleverly.
  • Branch and bound keeps a backtracking search but computes an optimistic bound for every partial solution, and abandons it when even the best case cannot beat the best answer found so far.

Neither is magic: the worst case stays exponential. But both turn problems you cannot run at all into problems you can, and they are the standard tools when n is around 30 to 40. They build on subsets and combinations, backtracking, and, for the combining step, binary search or hash tables.

Meet in the middle: the idea

Suppose you must decide something about all 2^n subsets of n items. Split the items into a left half L and a right half R of about n/2 items each. Every subset of the whole is a subset of L joined with a subset of R. So instead of enumerating all 2^n pairs, enumerate the 2^(n/2) subsets of each half and match them up.

TEXT
items:   [ a b c d | e f g h ]
          left half   right half
all subsets:        2^8 = 256
left subsets: 2^4 = 16     right subsets: 2^4 = 16

For n = 40 that is 2 x 2^20, about two million sums, against 2^40, over a trillion.

Subset sum: brute force first

Problem. Given a list of integers and a target, is there a subset that adds up to the target?

Brute force. Try every subset: O(2^n x n) if you re-add each time, or O(2^n) if you build sums incrementally.

Meet in the middle.

  1. Generate all subset sums of the left half, and of the right half.
  2. Put the right sums in a set (or a sorted list).
  3. For every left sum s, check whether target - s exists among the right sums.

Time O(2^(n/2)) with a hash set; space O(2^(n/2)).

Python Subset sum: brute force versus meet in the middle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second number in each tuple is the amount of sums generated. Brute force builds all 65,536 sums; meet in the middle builds 512. For n = 16 both are fast, but add 8 items and brute force grows 256 times larger while meet in the middle grows only 16 times.

If the numbers are small (say, their total is a few thousand), the knapsack dynamic programming approach is better: O(n x sum). Meet in the middle is the tool for large values with a small n.

Counting and closest sums

The same split answers harder questions.

Count the subsets that hit the target. Store the right sums in a Counter (sum -> how many subsets make it) and add counter[target - s] for each left sum.

Closest sum to the target. Sort the right sums. For each left sum s, binary search the right list for the value nearest to target - s. Total time O(2^(n/2) x n) because of the sort and the binary searches.

Python Counting subsets and the closest sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Another use: four-sum

Given four lists A, B, C, D, count the tuples with a + b + c + d == 0. Brute force is O(n^4). Meet in the middle: store every a + b in a dictionary (n^2 entries), then for every c + d look up -(c + d). The total is O(n^2): the split is "first two lists" versus "last two".

Branch and bound

Backtracking explores a tree of partial solutions. Branch and bound adds one question at every node: what is the best result this branch could possibly still reach? If even that optimistic number is no better than the best complete solution found so far, the whole subtree is skipped.

TEXT
              root
            /      \
        take A     skip A        <- branch
        /    \       /    \
   ...     ...    ...     ...

at each node:  bound(node) <= best_so_far ?  -> prune (do not explore)

The quality of the bound is everything. A weak bound prunes nothing; a bound that is too optimistic is fine (it is only less effective), but a bound that is ever too pessimistic is a bug, because it can cut away the true optimum.

Example: 0/1 knapsack with a fractional bound

Pick items to maximise value within a weight capacity. For a bound, pretend you may take fractions of the remaining items (the greedy fractional knapsack). That relaxed problem can only do better than the real one, so it is a valid optimistic bound. Sort the items by value/weight ratio so the bound is a simple greedy fill.

Python Knapsack: plain backtracking versus branch and bound

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions return the same optimum, because the bound only removes branches that provably cannot win. The plain search visits 349 nodes and the bounded one only 19. Two ingredients made that possible: sorting by ratio (so good solutions are found early and best rises quickly) and a cheap, tight bound.

Branch and bound on a tiny travelling salesman problem

Problem. A salesman must visit every city exactly once and return home. Find the shortest tour.

Brute force. Try every ordering of the other cities: (n-1)! tours.

Pruning. The cost so far is already a lower bound for the tour that extends it (distances are never negative). If the partial tour is as long as the best complete tour found, stop.

Python Tiny TSP with branch and bound

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 7 cities there are 6! = 720 tours, so brute force visits 1,957 nodes (all partial paths). Pruning with this simple bound (the cost so far) trims the count to 1,624 and keeps the same optimal cost. That is a modest saving because the bound is weak: it ignores the cities still to visit. Real solvers use much stronger bounds (minimum spanning tree or 1-tree bounds) and can handle dozens of cities; for exact answers on hundreds of cities, see dynamic programming with bitmasks and the hardness discussion in P, NP and hard problems.

Walkthrough: the 8-puzzle with least-cost branch and bound

The 8-puzzle has eight numbered tiles and one blank on a 3 x 3 board. A move slides a tile next to the blank into it. The goal is to reach 1 2 3 / 4 5 6 / 7 8 _ in as few moves as possible. There are 9! / 2 = 181,440 reachable boards, so even a blind search can finish, but the example shows exactly how a bound shrinks the work.

Least-cost branch and bound keeps a priority queue of partial solutions ordered by moves_so_far + bound, where bound is a lower bound on the moves still needed. It always expands the most promising node, so the first time it pops the goal, that path is optimal. (This is the algorithm better known as A*.) Two admissible bounds, meaning they never overestimate:

  • Misplaced tiles: each tile that is not home needs at least one move.
  • Manhattan distance: each tile needs at least as many moves as its row distance plus column distance from home. This is tighter, so it prunes more.

Half of all arrangements cannot reach the goal at all. A parity test on the number of inversions (pairs of tiles in the wrong order, ignoring the blank) says whether a board is solvable: for a 3 x 3 board the count must be even.

Python 8-puzzle: how much does a better bound save?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three find the same 14-move optimum, but the expanded boards drop from 4,158 with no bound to 302 with misplaced tiles and 77 with Manhattan distance. A tight, cheap, never-overestimating bound is exactly what the earlier knapsack and TSP examples were missing.

Complexity

Technique Time Space Needs
Brute force subset sum O(2^n) O(2^n) as built; O(n) with a recursive generator nothing
Meet in the middle O(2^(n/2)) with a hash set; O(2^(n/2) x n) with sorting O(2^(n/2)) the halves are independent and combinable
Branch and bound still exponential in the worst case O(depth) a valid, cheap, tight bound

Meet in the middle trades memory for time: those 2^(n/2) sums must be stored. For n = 40 that is about a million numbers per half, fine; for n = 60 it is a billion, too many.

When to use which

  • n up to about 20: plain backtracking or bitmask enumeration is enough.
  • n between 25 and 45 with values too big for a DP table: meet in the middle.
  • Optimisation problems where a relaxation gives a bound (fractional knapsack, minimum spanning tree for TSP): branch and bound.
  • Small values, large n: DP (subset sum) wins.

Common mistakes

  • Splitting unevenly. A 10/30 split still has 2^30 on one side. Split near the middle.
  • Forgetting the empty subset in each half (sum 0). [0] is the right starting list.
  • Counting twice. When counting subsets, every (left, right) pair is a distinct subset, so multiply counts; do not add them.
  • An invalid bound. If the bound is not truly optimistic, branch and bound silently returns wrong answers. Test it against brute force on small inputs.
  • Pruning too timidly. Prune with <=: when the bound only equals the best answer, the branch cannot improve it strictly, so exploring it is wasted work.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Meet in the middle turns a 2^n search into about:

    Each half has n/2 items, so each half has 2^(n/2) subsets. The total work is two such enumerations plus the combining step.
  2. 2. What is the main cost of meet in the middle compared with brute force?

    To match the halves you must store the sums of at least one half, so memory grows as 2^(n/2).
  3. 3. In branch and bound for a maximisation problem, a node is pruned when:

    If even the best possible completion of this branch cannot beat the best solution already found, exploring it is wasted work.
  4. 4. Why is the fractional knapsack a valid bound for the 0/1 knapsack?

    A relaxation that allows everything the real problem allows, plus more, can only do as well or better, so it is a safe optimistic bound.
  5. 5. For which input is dynamic programming on the sum a better choice than meet in the middle?

    DP costs O(n x sum), which is small when the sum is small, even for large n. Meet in the middle is for small n with huge values.

Summary

  • Meet in the middle splits the input, enumerates 2^(n/2) possibilities per half and combines them with a set, a counter or a sorted list plus binary search.
  • It trades memory for time and works when the two halves are independent.
  • Branch and bound is backtracking plus an optimistic bound; prune whenever the bound cannot beat the best answer so far.
  • A good bound comes from relaxing the problem (fractional items, minimum spanning tree) and from exploring promising branches first.
  • Both stay exponential in the worst case, but move the practical limit from n around 25 to n around 40 or more.

Next: Linear Search