3.7.16 · D5Algorithm Paradigms
Question bank — Backtracking — state-space tree, pruning
True or false — justify
Backtracking always finds the optimal solution.
False — plain backtracking enumerates all valid solutions or the first one; it has no built-in notion of "best". Adding a bound to keep the best-so-far turns it into Branch-and-Bound.
Pruning changes which solutions backtracking reports.
False — pruning only removes branches that provably contain no valid leaf, so the reported set of complete solutions is identical to brute force; only the runtime differs.
The worst-case time complexity of backtracking is always better than brute force.
False — an adversarial input may satisfy every partial check and prune nothing, so the worst case stays ; see Time-Complexity. Pruning helps the average case only.
Every node in the state-space tree is a complete solution.
False — only leaves are complete solutions (or dead-ends); internal nodes are partial solutions still under construction.
The state-space tree physically exists in memory during the search.
False — it is implicit. DFS holds only the current root-to-node path on the call stack; the tree is generated on the fly and never fully materialised.
Backtracking and Depth-First-Search are exactly the same algorithm.
False — backtracking is DFS over an implicit solution tree, but it adds an early feasibility prune and an explicit undo so one mutable state can be reused across branches.
If is_valid is always true, backtracking degenerates into full brute-force enumeration.
True — with nothing to prune, every one of the leaves is visited; the algorithm still terminates but does zero early-abandonment work.
Checking validity only at the leaf gives wrong answers.
False — it gives the same answers, but generates the entire tree first, so it is correct yet defeats the whole purpose of backtracking.
Moving the is_valid check earlier (higher in the tree) can never hurt correctness.
True if the test is monotonic — i.e. a violation at a partial state cannot be "un-violated" by future choices; then pruning early is always safe.
Spot the error
for c in candidates: state.add(c); backtrack(state) — what is missing?
The
state.remove(c) after the recursive call. Without the undo, the shared mutable state leaks into sibling branches and corrupts every subsequent choice.A student prunes if running_sum >= target in subset-sum with a positive target. Why is >= a bug?
It cuts the branch that exactly hits the target, discarding valid solutions. The correct prune is
> target, because equality is a solution to record, not a dead-end.Someone puts is_valid inside record at the leaf and claims it prunes. Why doesn't it?
A test at the leaf runs after the whole subtree above it was already generated, so it filters output but performs no pruning — no subtree was skipped.
state.remove(c) is placed before backtrack(state). What breaks?
The recursion then explores a state that no longer contains the choice just made, so the "explore" step sees the wrong partial solution — you undo before you've explored.
A subset-sum solver with negative numbers prunes on running_sum > target. Why is this unsafe?
With negatives, a large sum can later shrink below the target, so
sum > target is no longer a permanent violation — the prune is not monotonic and drops valid subsets.Two queens are placed and only the column clash is checked, not diagonals. What symptom appears?
Invalid boards survive to leaves and get recorded as "solutions"; the feasibility test is incomplete, so pruning fires too rarely rather than too often.
Why questions
Why does cutting one node kill exponentially many dead-ends?
An invalid partial choice poisons every leaf in its subtree; that subtree can hold up to leaves, so removing its root eliminates all of them in one stroke.
Why must the same state object be undone rather than copied fresh each call?
Reusing one mutable state is a memory/speed optimisation; the undo restores it to the parent's exact configuration so siblings start clean without paying to clone the whole state.
Why is the is_valid filter written inside the recursion's union, before the recursive call?
So the invalid choice's entire subtree is never generated. Testing before recursing is the pruning; testing after would generate then discard.
Why does pruning leave Big-O unchanged yet slash real runtime?
Big-O measures the worst case, and an adversarial input may prune nothing; typical inputs violate constraints early, so most branches die near the root, cutting actual work by huge factors.
Why is a "one queen per row" encoding smarter than "any queen anywhere"?
It bakes the no-two-in-a-row constraint into the branching itself, shrinking the branching factor and removing an entire class of invalid states before validity is even tested.
Why does backtracking use DFS rather than breadth-first order?
DFS follows one root-to-leaf path at a time, so only the current partial solution and its ancestors live on the stack — memory — whereas BFS would store a whole frontier of partial solutions.
Edge cases
A problem where no candidate is ever valid at the root — what does backtracking return?
The empty set of solutions; the root expands zero children, recursion unwinds immediately, and it correctly reports "no solution exists".
Subset-sum with target = 0 and all-positive elements — what is the answer?
The empty subset , whose sum is 0. A solver that forgets to record the empty state at depth 0 misses this valid solution.
N-Queens with — how many solutions?
One: the single queen on the single square, with no earlier rows to conflict, so the validity test is vacuously satisfied.
N-Queens with or — what happens?
Zero solutions; every placement clashes on a column or diagonal, so all branches prune to dead-ends and the search returns empty — a correct, not buggy, result.
A tree of depth 0 (state already complete at the root) — what does backtrack do?
is_complete is true immediately, so it records the root and returns without ever entering the candidate loop.If two distinct decision orders produce the same partial state, does backtracking deduplicate them?
No — plain backtracking treats them as separate tree paths and may record duplicate solutions; deduping needs an explicit visited-set or a canonical ordering of choices (see Permutations-and-Combinations).
Connections
- Parent topic — the derivation these traps stress-test.
- Branch-and-Bound — what backtracking becomes when you add an optimality bound.
- Dynamic-Programming — the alternative when overlapping subproblems (not just constraints) dominate.