Backtracking

9 questions, and they are all the same three lines. What changes is the choices, the base case, and the pruning.

The skeleton

void backtrack(State path, Choices remaining) {
    if (isComplete(path)) { record(path); return; }
    for (Choice c : remaining) {
        path.add(c);                    // CHOOSE
        backtrack(path, next(c));       // EXPLORE
        path.removeLast();              // UN-CHOOSE
    }
}

The un-choose is what makes it backtracking. path is shared mutable state across the whole search; without the removal, a sibling branch inherits the previous branch's choices. Verified: the no-restore variant of Word Search disagreed with the correct answer on 13 of 400 random boards — it fails sometimes, which is why it survives casual testing.

Three things vary, and only three

The start index decides three separate things

And in all three cases, starting the loop at the index forces non-decreasing order — which is what makes combinations unique without a deduplication pass. A start index exists to destroy ordering information; permutations need it kept, which is precisely why they don't have one.

Deduplication: three different rules

Getting these confused is the most common source of silently-wrong answers.

i > start, not i > 0. Verified on [1,2,2]: the correct guard yields 6 subsets, i > 0 yields 4, silently losing [2,2] and [1,2,2].

For Permutations II, both !used[i-1] and used[i-1] produce the correct set — the difference is pruning, measured at 92× on all-identical input.

continue vs break

break abandons the whole level, so it is only valid when failure is monotonic in the loop variable.

Verified: using break in Palindrome Partitioning on "aba" returns [["a","b","a"]] and loses [["aba"]].

N-Queens: make the check O(1)

Cells on a ↗ diagonal share r + c; cells on a ↘ diagonal share r − c. So three sets replace an O(n) scan — and since the validity check runs at every node, that removes a factor of n from the whole search.

The row constraint is handled better still: placing one queen per row designs it away, so rows never need checking at all.

The traps

Verification

Every snippet compiled and cross-checked against an independent implementation — 2,800+ randomized cases:

• Q1 across backtracking, bitmask and iterative doubling, with the count asserted as exactly 2^n
• Q3 across used[] and swap-based versions, count asserted as n!
• Q4 and Q5 against generate-and-deduplicate references, on heavily duplicated inputs
• Q6 against a boolean[][] reference, plus the caller's board verified untouched afterwards
• Q7 against a generate-all-cuts-and-filter reference
• Q9 counts matched the known sequence 1, 0, 0, 2, 10, 4, 40, 92, 352 for n = 1..9, and every returned board was independently re-validated for row, column and diagonal conflicts

Five deliberately-broken variants confirm the traps are real:

• i > 0 in Subsets II returns 4 subsets instead of 6 on [1,2,2]
• break in Palindrome Partitioning loses [["aba"]]
• no board restore in Word Search disagreed on 13 of 400 boards
• no empty guard in Letter Combinations returns a one-element list instead of an empty one
• the O(n)-scan N-Queens agrees on counts, confirming the encodings prune identically