Backtracking Technique: Concepts, Two Worked Examples and Exam Patterns

You may copy recursive code yet struggle to explain when a branch becomes impossible, why state must be undone, or which calls are explored. The useful model is choose, test, explore and undo. Exact 4-Queens and positive-integer subset-sum traces illustrate the model, while systematic search still permits exponential work.

Backtracking technique: choose, test, explore and undo

Backtracking constructs a candidate one decision at a time through depth-first search. After each choice, the partial state may be valid but incomplete, complete and successful, or already impossible. An impossible state is abandoned with every completion below it.

For a string using A, B and C, suppose adjacent symbols cannot match. From AB, trying B creates invalid ABB. Undo that B, restore AB, and try A to form valid ABA.

Recursion is an implementation mechanism, and brute force generates every complete candidate. Backtracking cuts a branch when a constraint proves no completion can succeed.

Backtracking state-space trees, invariants and a reusable template

In a state-space tree, the root is the empty sequence, an edge adds a choice, a node stores a partial candidate, and a leaf is a solution or dead end. Pruning removes the subtree below a node. DFS keeps only one active root-to-node path.

search(state):
    if complete(state):
        report or return

    for each choice in candidates(state):
        if safe(choice, state):
            apply(choice, state)
            search(state)
            undo(choice, state)

Before every loop iteration, state must equal its value before the previous candidate. Stop after one solution, enumerate all, or count them without changing the skeleton. Safety checks must use established prefix facts.

4-Queens worked example: reach the first solution step by step

Number rows and columns 1 to 4, place one queen per row, try columns left to right, and store columns in an array. Position (r,c) is safe when no earlier queen shares its column or satisfies |r-ri| = |c-ci|.

Place (1,1) to get [1]. In row 2, columns 1 and 2 fail by column and diagonal, so choose 3: [1,3]. Row 3 has no safe choice: 1 repeats row 1, 2 is diagonal to row 2, 3 repeats row 2, and 4 is diagonal to row 2.

Undo row 2 and choose 4: [1,4]. Row 3 column 2 gives [1,4,2]. Row 4 fails because 1 repeats row 1, 2 repeats row 3, 3 is diagonal to row 3, and 4 repeats row 2. Thus the branch rooted at [1] fails.

Next start with [2]. Row 2 columns 1, 2 and 3 fail; column 4 gives [2,4]. Row 3 column 1 gives [2,4,1], and row 4 column 3 gives the first solution [2,4,1,3].

Columns 2,4,1,3 are distinct. For queen pairs (1,2)-(2,4), (1,2)-(3,1), (1,2)-(4,3), (2,4)-(3,1), (2,4)-(4,3) and (3,1)-(4,3), the respective (row distance, column distance) values are (1,2), (2,1), (3,1), (1,3), (2,1) and (1,2). None are equal, so no pair is diagonal. The board is:

.Q..
...Q
Q...
..Q.

Subset sum worked example: include, exclude and prune

For positive values [3,4,5,2] and target 9, process in order and explore include before exclude. Store (index, chosen set, running sum). Prune when the sum exceeds 9, or when it plus all unprocessed values is below 9.

Start at sum 0: include 3 for 3, include 4 for 7, then include 5 for 12 and prune. Undoing 5 restores both {3,4} and sum 7; excluding 5 and including 2 reaches {3,4,2} at 9. To enumerate, finish that subtree, restore the root, exclude 3, include 4 and include 5 to get {4,5}.

The first pruning rule depends on positivity. With [8,-3,4], partial choice {8,4} totals 12, but a still-available -3 reaches 9. Negative values destroy monotonicity. Here subset sum is a depth-first feasibility search: each recursive return restores the chosen set and running sum, and pruning uses facts about the current prefix. A dynamic-programming solution instead stores reusable (item index, sum) states in a Boolean table.

Backtracking complexity: count the search space first

Backtracking has no single complexity. Branching factor b and depth d give up to 1 + b + ... + b^d nodes, or O(b^d) for b > 1. Pruning can shrink one tree without changing the worst case.

Four binary decisions give 1+2+4+8+16 = 31 nodes including the root and 2^4 = 16 complete subsets. Subset sum is O(2^n) worst case with O(n) DFS depth. N-Queens, excluding repeated columns, is bounded by O(N!) before diagonal pruning and uses O(N) path/state space excluding output.

Greedy commits without undoing, and dynamic programming stores repeated-state answers. Branch and Bound Explained: Bounds, Pruning and Worked Examples prunes nodes that cannot improve an incumbent; backtracking here rejects prefixes that constraints prove impossible. Hamiltonian paths and graph colouring, covered in Graph Theory: Euler, Hamiltonian, Coloring for GATE CS, are classic state-space searches.

Backtracking traps: why correct-looking code misses solutions

• Wrong move: forget to undo. Consequence: stale queen marks reject later branches. Repair: pair every mutation with its inverse.

• Wrong move: return on a dead end. Consequence: siblings are skipped. Repair: return early only after finding a solution in first-solution mode.

• Wrong move: guess a pruning rule. Consequence: valid answers disappear. Repair: prove the required input property.

• Wrong move: call pruning polynomial. Consequence: an observed smaller tree becomes a false bound. Repair: state the worst case separately.

Copying the board at every call increases storage and runtime constants. Scanning earlier queens is correct, but occupied-column and diagonal sets make checks faster.

Backtracking exam patterns: trace, validate, count and compare

Common tasks include finding the first ordered solution, identifying pruned nodes, counting calls or leaves, completing isSafe or undo logic, deriving complexity, and comparing techniques.

Use these checkpoints:

1. At queen state [2,4], row 3 column 1 is safe. It shares neither a column nor a diagonal with (1,2) or (2,4).

2. For [3,4,5,2] and target 9, the first include-first solution is {3,4,2}.

3. A binary-choice depth-4 tree has 16 complete candidates and at most 31 nodes including the root.

Graph MCQs: 10 Solved BFS, DFS, Connectivity (GATE) separates traversal order from constraint search. BFS and DFS set exploration order; backtracking adds construction, feasibility and undo. The GATE CS Exam Preparation route places this topic in the wider syllabus.

The short version and the next backtracking step

Remember five actions: represent state, choose, reject impossible prefixes, recurse on promising prefixes, and undo exactly. The first worked answers are [2,4,1,3] and {3,4,2}.

For practice, reverse the queen-column order; the first solution is [3,1,4,2]. Change the subset target to 10; 3+4 cannot be completed, while 3+5+2 gives the first solution {3,5,2}.

GATE Guidance by Sanchit Sir is a structured next step for placing backtracking beside other Algorithms. Keep the invariant: choose, test, explore, undo, and restore state before the next candidate.