Branch-and-bound, compared to backtracking, is specifically designed for:

Optimisation problems, pruning with a numeric bound against the best solution found so far

Decision problems only, with a validity check alone

Problems with no numeric objective at all

In the 0/1 knapsack solved by branch-and-bound, the bound at each node is typically computed by:

Solving the fractional relaxation of the remaining items

Ignoring all remaining items entirely

Always assuming the knapsack is empty

The comparison-tree argument proves that comparison-based sorting needs, in the worst case, at least:

Exactly n comparisons, never more

An infinite number of comparisons

Proving a lower bound for problem B by reduction from an already-known-hard problem A involves:

Transforming any instance of A into an instance of B cheaply, so a fast algorithm for B would yield one for A

Only applies to sorting problems

Which of the following are true of N-Queens solved by backtracking? (More than one option may be correct.)

A new queen's position is checked against every already-placed queen before it is accepted

On a conflict, the algorithm tries the next column in the current row

If no column in the current row works, it backtracks to the previous row

A new queen's position is checked against every already-placed queen before it is accepted

On a conflict, the algorithm tries the next column in the current row

If no column in the current row works, it backtracks to the previous row

It always places all N queens with no checking at all

The maximum-flow / minimum-cut style bound used to prune a branch-and-bound search subtree is discarded entirely when:

The bound exactly equals the best solution found so far

The subtree has never been visited before

The algorithm has not started yet

Backtracking, Branch-and-Bound and Lower Bound Theory

The course's Algorithms chapters cover divide-and-conquer, dynamic programming and greedy design. NET's Unit 7 also names backtracking and branch-and-bound as design techniques, and Lower Bound Theory (comparison trees, lower bounds through reductions) as a topic of its own. This chapter covers all three.

Backtracking

Backtracking builds a solution incrementally, one choice at a time, and abandons ('backtracks from') a partial solution the MOMENT it can be proven invalid or unpromising — rather than continuing to extend it and checking only at the end. This PRUNING is what separates backtracking from naive brute-force enumeration of every complete candidate: a bad partial choice is discarded before the (often exponentially many) ways of completing it are ever generated. The N-Queens problem is the canonical example — placing queens column by column and immediately rejecting a column position that attacks any already-placed queen, rather than placing all N queens first and checking the whole board afterward.

🎯 Backtracking's efficiency depends entirely on the pruning rule's strength

In the theoretical worst case, backtracking can still visit an exponential number of partial states if the pruning check is weak (e.g. it never actually rejects anything until a full assignment is reached, degenerating to brute force). Its practical speedup on problems like N-Queens, Sudoku or graph colouring comes from a STRONG, CHEAP-TO-CHECK rejection rule applied as early as possible in the search — the earlier a bad branch is cut, the more of the exponential tree beneath it is never explored at all.

Branch-and-Bound

Branch-and-bound also explores a search tree of partial solutions, but it targets OPTIMISATION problems (find the best solution, not just any valid one) and prunes using a numeric BOUND rather than a validity check alone: at each node it computes a bound on the best possible objective value reachable from that partial solution (an upper bound for maximisation, a lower bound for minimisation), and if that bound cannot beat the best complete solution found SO FAR, the whole subtree beneath that node is discarded without exploring it — this is exactly the technique already introduced for integer programming's LP-relaxation bound in Unit 1's Optimization chapter, applied here as a general algorithm-design technique rather than one specific to LP.

Backtracking versus branch-and-bound
Property	Backtracking	Branch-and-bound
Problem type	Decision/feasibility (any valid solution, or all of them)	Optimisation (the single BEST solution)
Pruning test	Is this partial state still valid/feasible?	Can this partial state's bound beat the best solution found so far?

Lower Bound Theory: Comparison Trees and Reductions

A comparison tree (decision tree) models any COMPARISON-BASED algorithm as a binary tree: each internal node is one comparison, each leaf is a possible final outcome/output, and the algorithm's WORST-CASE running time is at least the tree's HEIGHT, since some input forces a root-to-leaf path that long. Since a binary tree with height h has at most 2^h leaves, and the algorithm needs at least as many leaves as there are distinct possible outputs, height ≥ log₂(number of possible outputs) — this is exactly the argument that proves comparison-based sorting needs Ω(n log n) comparisons in the worst case: there are n! possible orderings, so height ≥ log₂(n!) = Ω(n log n) by Stirling's approximation.
Lower bounds through reduction: to prove that problem B is at least as hard as an ALREADY-KNOWN-hard problem A, show that A can be SOLVED by transforming (in a cost you can bound) any instance of A into an instance of B and calling a hypothetical algorithm for B — if B could be solved faster than A's known lower bound (plus the cheap transformation cost), A could be too, contradicting what is already known about A. This is the same reduction idea used throughout complexity theory (including NP-completeness proofs in the next chapter), just aimed here at proving a LOWER bound rather than classifying a decision problem.

⚠️ A lower bound is about EVERY algorithm, an upper bound about ONE algorithm

Proving that mergesort runs in O(n log n) is an UPPER bound on the SORTING PROBLEM (one algorithm achieves this). Proving comparison-based sorting needs Ω(n log n) comparisons is a LOWER bound on the sorting problem ITSELF (no comparison-based algorithm, however cleverly designed, can beat this). Since these two bounds MATCH (both n log n), comparison sorting is said to be OPTIMAL — a claim that could not be made from the upper bound alone, since a faster algorithm might still be waiting to be discovered until the matching lower bound rules that out.

Worked Examples: N-Queens, 0/1 Knapsack and Sudoku

N-Queens by backtracking: place one queen per row, column by column within that row; before placing, check the new position against every already-placed queen for same-column or same-diagonal conflict (an O(1)-per-check test using row/column/diagonal difference); on conflict, try the next column in that row; if no column in the current row works, backtrack to the previous row and try its next option.
0/1 Knapsack by branch-and-bound: at each node (a partial decision on some prefix of items), compute an upper bound on achievable value by taking the FRACTIONAL relaxation of the remaining items sorted by value-to-weight ratio (the same greedy bound the fractional knapsack solves exactly) — since this fractional bound is always at least the true 0/1 optimum reachable from that node, any node whose bound falls below the best 0/1 solution found so far can be pruned entirely.
Sudoku by backtracking: fill cells in a fixed order; before placing a digit, check row, column and 3×3 box for a repeat — an immediate, cheap constraint check that discards a huge fraction of the search tree before it is ever generated, which is exactly the pruning-strength point from the earlier note.

Key takeaways

Backtracking abandons a partial solution the moment it is provably invalid, pruning before exhaustive enumeration; a weak pruning rule degenerates it toward brute force.
Branch-and-bound prunes optimisation-problem subtrees using a numeric bound compared against the best complete solution found so far — the same idea as integer programming's LP-relaxation bound, generalised.
A comparison tree's height lower-bounds a comparison-based algorithm's worst case; this proves comparison sorting needs Ω(n log n) comparisons.
A lower bound via reduction shows problem B is at least as hard as an already-known-hard problem A by transforming A into B cheaply.
A lower bound constrains every possible algorithm; an upper bound is achieved by one algorithm — matching bounds prove optimality.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

Backtracking differs from naive brute-force enumeration of every complete candidate chiefly because it:
1. Abandons a partial solution the moment it is provably invalid, before generating the ways of completing it
2. Always visits every possible complete candidate regardless
3. Never checks any partial state
4. Requires no problem-specific validity check at all
Show answer
Answer: A — Abandons a partial solution the moment it is provably invalid, before generating the ways of completing it
The pruning check applied to a partial (incomplete) solution is exactly what avoids generating the exponentially many complete candidates that extend an already-invalid partial one.
Branch-and-bound, compared to backtracking, is specifically designed for:
1. Optimisation problems, pruning with a numeric bound against the best solution found so far
2. Decision problems only, with a validity check alone
3. Problems with no numeric objective at all
4. Sorting problems exclusively
Show answer
Answer: A — Optimisation problems, pruning with a numeric bound against the best solution found so far
Branch-and-bound targets finding the single best solution to an optimisation problem, using a bound on the best achievable objective value from a partial state to decide whether that subtree is worth exploring at all.
In the 0/1 knapsack solved by branch-and-bound, the bound at each node is typically computed by:
1. Solving the fractional relaxation of the remaining items
2. Ignoring all remaining items entirely
3. Always assuming the knapsack is empty
4. Randomly guessing a number
Show answer
Answer: A — Solving the fractional relaxation of the remaining items
The fractional knapsack's greedy solution gives a value that is always at least as good as the true 0/1 optimum reachable from that node, making it a valid (and cheap to compute) upper bound for pruning.
The comparison-tree argument proves that comparison-based sorting needs, in the worst case, at least:
1. Ω(n log n) comparisons
2. Exactly n comparisons, never more
3. Zero comparisons
4. An infinite number of comparisons
Show answer
Answer: A — Ω(n log n) comparisons
With n! possible orderings as leaves of the comparison (decision) tree, the tree's height must be at least log₂(n!), which by Stirling's approximation is Ω(n log n).
Proving a lower bound for problem B by reduction from an already-known-hard problem A involves:
1. Transforming any instance of A into an instance of B cheaply, so a fast algorithm for B would yield one for A
2. Proving A is easy, not hard
3. Ignoring problem A entirely
4. Only applies to sorting problems
Show answer
Answer: A — Transforming any instance of A into an instance of B cheaply, so a fast algorithm for B would yield one for A
If B could be solved faster than A's known lower bound (plus the cheap transformation), A could be solved that fast too — contradicting what is already known about A, which forces B to be at least as hard.
Which of the following are true of N-Queens solved by backtracking? (More than one option may be correct.)
1. A new queen's position is checked against every already-placed queen before it is accepted
2. On a conflict, the algorithm tries the next column in the current row
3. If no column in the current row works, it backtracks to the previous row
4. It always places all N queens with no checking at all
Show answer
Answer: A — A new queen's position is checked against every already-placed queen before it is accepted; B — On a conflict, the algorithm tries the next column in the current row; C — If no column in the current row works, it backtracks to the previous row
The check-then-place-or-retry-or-backtrack cycle is exactly the backtracking mechanism; placing all queens with no checking would instead be brute-force enumeration with validity checked only at the end.
Name the tree used to model any comparison-based algorithm, whose height lower-bounds the algorithm's worst-case running time.
Numerical answer — type the value.
Show answer
Answer: comparison tree
The comparison (decision) tree's leaves correspond to possible outputs, and since a binary tree of height h has at most 2^h leaves, the height must be at least the log of the number of possible outputs.
The maximum-flow / minimum-cut style bound used to prune a branch-and-bound search subtree is discarded entirely when:
1. The bound cannot beat the best complete solution found so far
2. The bound exactly equals the best solution found so far
3. The subtree has never been visited before
4. The algorithm has not started yet
Show answer
Answer: A — The bound cannot beat the best complete solution found so far
A subtree whose best-case bound is already worse than a solution already in hand cannot possibly contain anything better, so it is safe to discard the entire subtree without exploring it.