Branch & Bound and Meet in the Middle

The previous lessons built backtracking: a depth-first walk over a tree of partial solutions that prunes a branch the moment it becomes infeasible, such as a queen attacking another or a graph coloring conflict. That kind of pruning asks a yes/no question: can this partial solution still be completed at all? For optimization problems, maximize this or minimize that, we can ask a sharper question: even in the best case, can completing this partial solution beat the best answer I already have? If not, the entire subtree is dead, feasible or not. Pruning by value rather than mere feasibility is the idea behind branch and bound, and it often cuts the running time by many orders of magnitude.

When even aggressive pruning is not enough, when the search tree is genuinely $2^n$-shaped and $n$ is, say, $36$, a second technique buys a square root of the running time outright. Meet in the middle splits the instance, enumerates each half independently, and stitches the halves back together with sorting and binary search. Both techniques attack the exponential running time, from different sides.

Branch and bound: pruning by value

Branch and bound is backtracking with two extra pieces of bookkeeping. The first is the incumbent: the value (and witness) of the best complete solution found anywhere in the search so far. The second is a bound computed at every node, an optimistic estimate of the best objective achievable by any completion of that partial solution. For a maximization problem the bound is an upper bound (no completion can do better than this); for minimization it is a lower bound.

A bound is sound exactly when this holds — when it never prunes a subtree that contains an optimum. An optimistic bound guarantees soundness, so branch and bound stays complete for the optimization problem: the optimal solution survives every cut and is eventually reported. A bound that could under-estimate (maximization) would be unsound, silently discarding the answer.

The method's effectiveness depends entirely on two design choices. A tighter bound prunes more nodes; a bound equal to the true optimum would prune everything but the answer. And a better search order, finding a strong incumbent early, raises $z^{\ast }$ sooner, which retroactively prunes more of the tree. The two interact: a good incumbent makes a mediocre bound effective.

The right subtree carries bound $29\le z^{\ast }=38$, so it is pruned without ever being expanded; the blue path is the active best completion that established the incumbent.

Worked example: 0/1 knapsack by branch and bound

We have $n$ items with values $v_i$ and weights $w_i$ and a capacity $W$; choose a subset of maximum total value with total weight $\le W$. The decision tree is binary, take item $i$ or skip it, so it has $2^n$ leaves. To bound a node, we use the LP relaxation: relax the integrality constraint and allow a fraction of the next item. First order all items by value density$v_i/w_i$, descending. At a node that has fixed a prefix of decisions, with accumulated value $V$ and remaining capacity $c$, greedily fill $c$ with the not-yet-decided items in density order, taking the last one fractionally:

where $F_{\text{full}}$ are the remaining items that fit wholly and $j$ is the first item that overflows (filled fractionally). This fractional fill is the optimal solution to the relaxed problem, so it can only over-estimate the integral optimum, which is the optimism a sound bound requires.²

Branching on take before skip tends to find a heavy, valuable incumbent early, which makes the bound bite sooner. Compare this against the dynamic-programming solution. The DP runs in $\Theta (nW)$ time, pseudo-polynomial, because $W$ enters as a magnitude, not a bit-length. When $W$ is enormous (say weights are $9$-digit numbers) the DP table is hopeless, yet if $n$ is moderate the branch-and-bound tree, heavily pruned, finishes quickly. The two methods are complementary: DP wins when $W$ is small; branch and bound wins when $W$ is huge but $n$ is moderate.

Branching take-first dives straight to the incumbent $\{A,B\}$ with value $z^{\ast }=22$. The skip-$A$ subtree's optimistic LP bound is only $16$ (take $B$ whole, then $\frac{2}{3}$ of $C$: $12+2\cdot \frac{6}{3}=16$), which cannot beat $22$, so the entire right half is discarded before a single completion is built.

from typing import NamedTuple, Sequence

class Item(NamedTuple):
  """
    One knapsack item: the value gained and the weight it costs.\n
  """
  value: float
  weight: float

def _density(item: Item) -> float:
  """
    Value per unit weight; a zero-weight item is infinitely dense.\n
  """
  return float("inf") if item.weight == 0 else item.value / item.weight

def _bound(
  ordered: Sequence[Item],
  index: int,
  value_so_far: float,
  weight_so_far: float,
  capacity: float,
) -> float:
  """
    Optimistic upper bound for the node fixing items `0..index-1`.\n
    Greedily fill the remaining capacity with the undecided items in\n
    density order, slicing the first overflowing item fractionally. That\n
    fractional fill solves the LP relaxation, so it can only over-estimate\n
    the best integral completion.\n
  """
  bound: float = value_so_far
  remaining: float = capacity - weight_so_far

  # take whole items in density order until one overflows.
  for position in range(index, len(ordered)):
    item = ordered[position]
    if item.weight <= remaining:
      bound += item.value
      remaining -= item.weight
    else:
      # slice the overflowing item to exactly fill what is left.
      bound += remaining * _density(item)
      break

  return bound

def knapsack_branch_and_bound(
  items: Sequence[Item],
  capacity: float,
) -> float:
  """
    Best total value of a subset of `items` whose weights fit within\n
    `capacity`, found by depth-first branch and bound.\n
  """
  if capacity < 0:
    return 0.0

  # density order makes the fractional bound exact for the relaxation.
  ordered: list[Item] = sorted(items, key=_density, reverse=True)
  count: int = len(ordered)
  incumbent: float = 0.0

  def expand(index: int, value_so_far: float, weight_so_far: float) -> None:
    nonlocal incumbent

    # abandon overweight nodes, then bank this node's value if it leads.
    if weight_so_far > capacity:
      return
    if value_so_far > incumbent:
      incumbent = value_so_far
    if index == count:
      return

    # prune by value: no completion here can beat what we already hold.
    if _bound(ordered, index, value_so_far, weight_so_far, capacity) <= incumbent:
      return

    item = ordered[index]

    # branch take-first: dives toward a heavy incumbent that prunes hard.
    expand(index + 1, value_so_far + item.value, weight_so_far + item.weight)
    expand(index + 1, value_so_far, weight_so_far)

  expand(0, 0.0, 0.0)
  return incumbent

Search order: depth-first vs best-first

The skeleton above is depth-first branch and bound: it recurses to a leaf fast, so it finds some complete solution, an incumbent, almost immediately, and it uses only $O(n)$ stack. The cost is that the first incumbent may be poor, weakening early pruning. The alternative is best-first search: keep a priority queue of live nodes keyed by their bound, and always expand the node with the most promising bound. Best-first tends to drive toward the optimum with the fewest expansions and, for many problems, expands the optimal node first, but it can hold an exponential frontier of live nodes in the queue, so its memory is the liability. The practical compromise is to seed the incumbent with a quick greedy solution, then run depth-first with strong bounds: cheap memory, and a floor high enough that the bound prunes hard from the start.

Depth-first (left) follows one accented path to a leaf, banking an incumbent fast while holding only the current root-to-node stack. Best-first (right) instead pops the live node of highest bound ($37>29$) from a priority queue, steering toward the optimum in fewer expansions at the cost of keeping the whole frontier in memory.

import heapq
from itertools import count
from typing import NamedTuple, Sequence

class Item(NamedTuple):
  """
    One knapsack item: the value gained and the weight it costs.\n
  """
  value: float
  weight: float

class LiveNode(NamedTuple):
  """
    A node awaiting expansion: how far decisions are fixed, the value and\n
    weight accumulated, and the optimistic bound that orders the queue.\n
  """
  position: int
  value_so_far: float
  weight_so_far: float
  bound: float

def _density(item: Item) -> float:
  """
    Value per unit weight; a zero-weight item is infinitely dense.\n
  """
  return float("inf") if item.weight == 0 else item.value / item.weight

def _bound(
  ordered: Sequence[Item],
  index: int,
  value_so_far: float,
  weight_so_far: float,
  capacity: float,
) -> float:
  """
    Optimistic upper bound: greedily fill the remaining capacity with the\n
    undecided items in density order, slicing the first overflowing item\n
    fractionally (the LP relaxation, an over-estimate of the integer optimum).\n
  """
  bound: float = value_so_far
  remaining: float = capacity - weight_so_far

  # take whole items in density order, slicing the first overflow.
  for position in range(index, len(ordered)):
    item = ordered[position]
    if item.weight <= remaining:
      bound += item.value
      remaining -= item.weight
    else:
      bound += remaining * _density(item)
      break

  return bound

def best_first_knapsack(items: Sequence[Item], capacity: float) -> float:
  """
    Best total value of a subset of `items` fitting within `capacity`,\n
    found by best-first branch and bound (highest bound expanded first).\n
  """
  if capacity < 0:
    return 0.0

  # density order makes the fractional bound exact for the relaxation.
  ordered: list[Item] = sorted(items, key=_density, reverse=True)
  total: int = len(ordered)
  incumbent: float = 0.0

  # heapq is a min-heap; negate the bound to pop the largest first. The
  # monotonic tie-breaker keeps NamedTuples off the comparison path.
  tie_breaker = count()
  frontier: list[tuple[float, int, LiveNode]] = []

  def push(node: LiveNode) -> None:
    heapq.heappush(frontier, (-node.bound, next(tie_breaker), node))

  root_bound: float = _bound(ordered, 0, 0.0, 0.0, capacity)
  push(LiveNode(0, 0.0, 0.0, root_bound))

  while frontier:
    negated_bound, _, node = heapq.heappop(frontier)

    # every remaining live node is at least this good; if even the best
    # cannot beat the incumbent, the whole frontier is hopeless.
    if -negated_bound <= incumbent:
      break
    if node.position == total:
      continue

    item = ordered[node.position]

    # child that takes the current item, if it still fits.
    taken_weight: float = node.weight_so_far + item.weight
    if taken_weight <= capacity:
      taken_value: float = node.value_so_far + item.value
      incumbent = max(incumbent, taken_value)

      # queue the child only while its bound can still beat the incumbent.
      taken_bound: float = _bound(
        ordered, node.position + 1, taken_value, taken_weight, capacity
      )
      if taken_bound > incumbent:
        push(LiveNode(node.position + 1, taken_value, taken_weight, taken_bound))

    # child that skips the current item.
    skip_bound: float = _bound(
      ordered, node.position + 1, node.value_so_far, node.weight_so_far, capacity
    )
    if skip_bound > incumbent:
      push(
        LiveNode(
          node.position + 1, node.value_so_far, node.weight_so_far, skip_bound
        )
      )

  return incumbent

Meet in the middle

Some problems resist pruning entirely: the bound is weak, the structure symmetric, every branch genuinely live. If the instance is a subset problem over $n$ items and $n\le 40$, meet in the middle sidesteps pruning and attacks the exponent directly. Split the items into two halves $A$ and $B$ of size $\approx n/2$. Enumerate all $2^{n/2}$ subset sums of $A$ into a list $S_A$, and likewise all subset sums of $B$ into $S_B$. Every subset of the whole is one choice from $A$ paired with one from $B$, so the full answer is recovered by combining one element of $S_A$ with one of $S_B$, but we perform that combination efficiently, not by trying all $2^{n/2}\cdot 2^{n/2}=2^n$ pairs.

For the canonical task, find a subset whose sum is closest to a target $T$ (this is the minimum-partition-difference problem with $T=({\sum }_i{x}_i)/2$), sort $S_B$, then for each $a\in S_A$ binary-search $S_B$ for the value nearest $T-a$. Each query is $O(\log 2^{n/2})=O(n)$, so the whole combine is $O(2^{n/2}n)$.

The enumeration is $O(2^{n/2})$ per half, the sort is $O(2^{n/2}n)$, and the combine is $O(2^{n/2}n)$, so the whole algorithm is $O(2^{n/2}n)$, a quadratic improvement over the $O(2^n)$ brute force. Concretely, $2^{40}$ is about $10^{12}$ (out of reach) while $2^{20}$ is about $10^6$ (instant). The technique is exact, no approximation and no pruning luck, and it is the intended solution to every Hard subset problem in this lesson's practice set.

For each sum $a$ on the top we binary-search the sorted bottom list for $T-a$; the blue pair $5+6=11$ hits the target exactly. To see the whole method end to end, take the eight numbers $[3,34,4,12,5,2,1,9]$ and target $T=20$. Split into $A=[3,34,4,12]$ and $B=[5,2,1,9]$. Enumerating every subset sum:

• $S_A=\{0,3,4,7,12,15,16,19,34,37,38,41,46,49,50,53\}$ (the $2^4=16$ sums of $A$).
• $S_B=\{0,1,2,3,5,6,7,8,9,10,11,12,14,15,16,17\}$ (sorted).

Now walk $S_A$: for $a=4$ we seek $T-a=16$ in $S_B$, and $16$ is present, so $4+16=20$ hits the target exactly — the subset $\{4\}$ from $A$ plus $\{2,5,9\}$ from $B$. The combine did $16$ binary searches of a $16$-element list instead of scanning all $2^8=256$ subsets, and it scales: at $n=40$ it is $2^{20}\approx 10^6$ searches rather than $2^{40}\approx 10^{12}$ subsets.

The same split-and-recombine idea is the graph analog bidirectional search: to find a shortest path, run BFS forward from the source and backward from the target simultaneously and stop when the two frontiers meet, exploring $\approx 2\cdot b^{d/2}$ nodes instead of $b^d$.

from bisect import bisect_left
from typing import Sequence

def _subset_sums(items: Sequence[float]) -> list[float]:
  """
    Every subset sum of `items`, including the empty subset (sum 0).\n
    Built by doubling: each new item either extends or skips every sum\n
    seen so far, giving 2^len(items) sums in total.\n
  """
  sums: list[float] = [0.0]
  for item in items:
    sums += [existing + item for existing in sums]
  return sums

def closest_subset_sum(items: Sequence[float], target: float) -> float:
  """
    The subset sum of `items` nearest to `target` (its absolute distance is\n
    minimized). The empty subset, with sum 0, is always a candidate.\n
  """
  # enumerate one half, sort the other so it can be binary-searched.
  midpoint: int = (len(items) + 1) // 2
  left_sums: list[float] = _subset_sums(items[:midpoint])
  right_sums: list[float] = sorted(_subset_sums(items[midpoint:]))

  best_distance: float = float("inf")
  for left_sum in left_sums:

    # the right sum nearest the complement sits at one of two neighbours.
    complement: float = target - left_sum
    position: int = bisect_left(right_sums, complement)

    # check both neighbours, keeping the closest total to the target.
    for neighbour in (position - 1, position):
      if 0 <= neighbour < len(right_sums):
        total: float = left_sum + right_sums[neighbour]
        best_distance = min(best_distance, abs(total - target))

  return best_distance

def min_partition_difference(items: Sequence[float]) -> float:
  """
    The smallest achievable difference between the sums of two groups that\n
    partition `items`. Reduces to a closest-subset-sum query with target\n
    half the total: a subset summing to `total/2` splits the items evenly,\n
    and a subset sum `s` leaves a difference of |total - 2*s|.\n
  """
  total: float = sum(items)
  best_distance: float = closest_subset_sum(items, total / 2)

  # distance from total/2 is half the resulting partition gap.
  return 2 * best_distance

from collections.abc import Hashable
from typing import Optional, TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

def _stitch_path(
  meeting_label: Label,
  parent_from_source: dict[Label, Optional[Label]],
  parent_from_target: dict[Label, Optional[Label]],
) -> list[Label]:
  """
    Rebuild the full path from the label where the frontiers met, walking\n
    the source-side parents backward and the target-side parents forward.\n
  """
  # walk source-side parents back to the source, then flip to read forward.
  forward: list[Label] = []
  cursor: Optional[Label] = meeting_label
  while cursor is not None:
    forward.append(cursor)
    cursor = parent_from_source[cursor]
  forward.reverse()

  # walk target-side parents forward to the target.
  backward: list[Label] = []
  cursor = parent_from_target[meeting_label]
  while cursor is not None:
    backward.append(cursor)
    cursor = parent_from_target[cursor]

  return forward + backward

def bidirectional_search(
  graph: Graph[Label],
  source: Label,
  target: Label,
) -> Optional[list[Label]]:
  """
    A shortest (fewest-edges) path from `source` to `target`, or None if no\n
    path exists. Edge weights are ignored; this counts hops. The returned\n
    list begins at `source` and ends at `target`.\n
  """
  if source not in graph or target not in graph:
    return None
  if source == target:
    return [source]

  # the forward side follows outgoing edges; the backward side must follow
  # edges *into* a vertex, so precompute a reverse adjacency once. For an
  # undirected graph the two coincide, but a digraph needs the distinction.
  predecessors: dict[Label, list[Label]] = {label: [] for label in graph.labels}
  for edge in graph.edges():
    predecessors[edge.target.label].append(edge.source.label)
    if not graph.directed:
      predecessors[edge.source.label].append(edge.target.label)

  def successors(label: Label) -> list[Label]:
    return [neighbor.label for neighbor in graph.vertex(label).neighbors()]

  # each side records, for every reached label, the neighbour it came from
  # (None at that side's own root) so a path can be stitched together.
  parent_from_source: dict[Label, Optional[Label]] = {source: None}
  parent_from_target: dict[Label, Optional[Label]] = {target: None}
  source_frontier: list[Label] = [source]
  target_frontier: list[Label] = [target]

  while source_frontier and target_frontier:

    # always expand the smaller frontier to keep the search balanced.
    expand_source: bool = len(source_frontier) <= len(target_frontier)
    frontier = source_frontier if expand_source else target_frontier

    # `seen` is this side's parents; `other_seen` is where we hope to collide.
    seen = parent_from_source if expand_source else parent_from_target
    other_seen = parent_from_target if expand_source else parent_from_source

    next_frontier: list[Label] = []
    for label in frontier:

      # follow edges in this side's direction, skipping already-seen labels.
      adjacent: list[Label] = (
        successors(label) if expand_source else predecessors[label]
      )
      for neighbor_label in adjacent:
        if neighbor_label in seen:
          continue
        seen[neighbor_label] = label

        # the two searches touch here: stitch the discovered halves.
        if neighbor_label in other_seen:
          return _stitch_path(
            neighbor_label, parent_from_source, parent_from_target
          )
        next_frontier.append(neighbor_label)

    if expand_source:
      source_frontier = next_frontier
    else:
      target_frontier = next_frontier

  return None

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

When to reach for which

The three pruning disciplines line up neatly along one axis: what justifies discarding a branch.

• Backtracking prunes by feasibility: a partial solution that violates a constraint can never be completed, so cut it.
• Branch and bound prunes by value: a partial solution whose optimistic bound cannot beat the incumbent is pointless to complete, so cut it.
• Meet in the middle prunes nothing; it instead trades exponential time for the square root of it, $2^n\to 2^{n/2}$, paying with $O(2^{n/2})$ memory to store the enumerated half.

Branch and bound works best when a cheap, tight optimistic bound exists (knapsack's LP fill, a TSP node's spanning-tree lower bound). Meet in the middle works best when no such bound exists but $n$ is small enough that $2^{n/2}$ is affordable. Both are exact; neither changes the worst-case exponential complexity; both routinely turn an infeasible instance into a feasible one.

How the world actually solves hard optimization

Branch and bound solves the large integer programs behind logistics, scheduling, and network design every day.

Branch and cut. Modern integer-programming solvers — CPLEX, Gurobi, the open-source SCIP — run branch and cut: branch and bound whose LP-relaxation bound (exactly the knapsack bound of this lesson, generalized) is tightened at each node by adding cutting planes, linear inequalities valid for all integer solutions but violated by the current fractional optimum.³ Gomory's cuts (1958) and the Padberg–Rinaldi cuts for the traveling salesman turned instances once deemed hopeless into routine ones; a combination of branch and cut solved a TSP over all $85,900$ cities of a VLSI application to proven optimality.⁴ The engineering lesson matches this lesson's theory: a tighter bound (better cuts) and a stronger incumbent (better heuristics) each prune more of the tree.

A*: the same idea. Best-first branch and bound is, essentially, the A* search algorithm (Hart, Nilsson & Raphael, 1968): expand the live node minimizing $f=g+h$, where $g$ is the cost so far and $h$ is an admissible heuristic — a bound that never overestimates the remaining cost.⁵ Admissibility supplies the optimistic-bound condition that makes pruning sound here; A* is branch and bound with the objective shortest path and the bound

Meet in the middle in cryptanalysis. The meet-in-the-middle split is older than its algorithmic-puzzle use: Diffie and Hellman (1977) introduced it to attack double encryption, showing that encrypting twice with two keys gives far less than double the security because an attacker enumerates each key-half and matches in the middle — the same $2^n\to 2^{n/2}$ collapse, applied to key search.⁶ The subset trick and the cryptographic attack are the same idea.

Takeaways

• Branch and bound is backtracking for optimization: maintain an incumbent (best complete solution so far) and a bound (optimistic estimate per node), and prune any node whose bound cannot beat the incumbent.
• The method's power is all in the bound tightness and search order: a tighter bound and an earlier strong incumbent each prune more of the tree.
• For 0/1 knapsack, order by density $v_i/w_i$ and bound by the LP-relaxation fractional fill; branch and bound beats the $\Theta (nW)$ DP when $W$ is huge but $n$ is moderate.
• Depth-first branch and bound finds an incumbent fast with $O(n)$ memory; best-first (priority queue on bound) targets the optimum with fewer expansions but can hold an exponential frontier.
• Meet in the middle enumerates each of two halves ($2^{n/2}$ subset sums) and recombines by sorting + binary search, giving $O(2^{n/2}n)$, exact search up to $n\approx 40$; bidirectional search is the graph analog.
• One axis: backtracking prunes by feasibility, branch and bound by value, meet in the middle trades exponential time for ​ of it at the cost of memory.