Question bank — Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

False — in the worst case (no branch can ever be pruned, e.g. permutations where every ordering is valid) it visits the same full tree; pruning only helps when constraints let you kill branches early.

False — backtracking specifically mutates a shared state and then restores it (choose → explore → un-choose); plain recursion may pass fresh copies and never undo anything.

False — it gives wrong answers: leftover choices leak into sibling branches, so later results inherit garbage (e.g. queens still "placed" on the board).

False — it stores a reference to one list that keeps mutating, so all your saved answers end up identical (usually all empty), which is a correctness bug not a memory one.

False — subsets branch into a binary "take/skip" tree with $2^n$ leaves; permutations branch into a shrinking $n,n-1,\dots$ tree with $n!$ leaves, and permutations need a used array while subsets need only an index.

False — N-Queens (as written) collects all solutions and returns nothing, exploring every branch; the Sudoku solver wants one solution and returns a bool to short-circuit the moment a full fill succeeds.

False — it loses nothing: any valid solution has exactly one queen per row anyway (two in a row would attack), so we only remove branches that were guaranteed invalid.

False — leaf-only checking is essentially brute force; you generate every doomed configuration fully before rejecting it, throwing away backtracking's entire advantage.

True in correctness, but scanning costs $O(n)$ per check versus $O(1)$ for the array — same answers, worse constant factor.

False — r-c catches only the ↘ diagonals; ↗ attacks share a constant r+c, so without the anti-diagonal set two queens on a ↗ line slip through undetected.

Error — N-Queens must collect every solution, so returning early would abandon sibling columns and miss valid boards; early-return is only correct when you want a single answer (like Sudoku).

Error — length is irrelevant; every appended reference points to the same mutating list, so after recursion finishes all entries read as []; you must append path[:].

Error — it's used once per branch, not once total; without used[i]=False on the way up, later top-level branches ("start with 2") can never reuse element 1.

Error — that isn't the box; the box index is (r//3)*3 + c//3, and inside it you must iterate cells (b//3)*3 + i//3, (b%3)*3 + i%3 — using r*3+c mixes up cell coordinates with box coordinates.

Error — the row constraint requires scanning all columns i in that row (and all rows in that column); checking one cell validates nothing.

Error — the sets are what give $O(1)$ conflict checks; if they aren't updated alongside the board, later rows won't see the queen and will place attackers.

Error — without the pop, the taken element leaks into the sibling "skip" branch's state, corrupting every subsequent subset.

Because the choices multiply: $2$ options for the first element $\times 2$ for the second $\times \dots$ over all $n$ elements $=2^n$ total combinations, one per subset.

Moving down-right adds $1$ to both r and c, so their difference $r-c$ never changes; that single number therefore labels the whole diagonal.

Sudoku wants one solution and uses True to stop all further searching the instant it's found; N-Queens wants all solutions, so it never short-circuits and just records each one.

Validating first lets a dead branch die at its root before we generate its whole subtree — that early death is exactly the pruning that separates backtracking from brute force.

It removes all row-conflicts for free and cuts the branching factor from $N^2$ candidate squares down to $N$ columns per row, shrinking the tree dramatically.

In a maze you walk back only to the last fork and try another path rather than restarting; backtracking likewise undoes just the most recent choice and tries the next sibling, reusing all the correct work above it.

Because the parent node's partial solution is still valid and shared by all its children; you only undo your increment so the next sibling inherits the same correct prefix.

Exactly one subset — the empty set [[]] — because with $n=0$ there are $2^0=1$ subsets and the base case records the empty path.

One permutation, the empty ordering [[]], since $0!=1$ and len(path) == len(nums) is immediately true.

No — both are impossible; the tree is fully explored and res comes back empty, which is a correct result, not a bug.

bt() finds no empty cell, so it immediately hits the "no empty cell → solved" branch and returns True without changing anything.

Every digit fails at some empty cell, each level returns False, the recursion unwinds fully, and the board is left restored to its original .-filled state.

The plain used-array version produces duplicate orderings ([1,1] twice) because it only tracks positions, not values; deduping needs an extra "skip equal siblings" rule beyond this template.

The for loop body never runs, the function returns having recorded nothing, and control unwinds to the parent — a natural dead-end handled with no special code.