Backtracking Technique Interview Questions and Answers: Trace, Prune and Explain

Backtracking questions test whether you can define a recursive state, prove a prune is safe, restore shared state, and derive the search cost. During a trace, narrate choose -> explore -> unchoose while the state changes; subset sum exposes pruning and copying, while N-Queens exposes constraint checks. The Coding & DSA curriculum supplies broader practice after these interview drills.

1. What is backtracking? Give the interview answer in four parts

A concise model answer is: "Backtracking explores a decision tree depth first. At each level it makes one valid choice, recurses, then reverses that choice before trying the next one. It cuts a branch as soon as the partial state cannot lead to a valid answer."

The reversal matters when sibling calls share a list, board, or visited set. Without it, a later branch starts with choices made by an earlier branch.

Keep four related ideas separate. Recursion is the call mechanism. DFS is the traversal order. Backtracking combines that traversal with constraint checks and state restoration. Pruning is safe only when an invariant proves that a discarded branch cannot succeed.

Before coding, ask four questions:

1. What does the state contain?

2. What choices are available at this depth?

3. What makes a partial state invalid or complete?

4. Which mutation must be undone before trying a sibling choice?

2. Trace subset sum completely: [3,1,4,2], target 6

Define search(i, sum, picked) precisely. Indices below i have been decided, sum is their total, and picked contains their values. Since every value is positive, sum > 6 is a sound prune. That proof would not hold if negative values were allowed.

Trace the first successful branch:

• Start at (i=0, sum=0, []).

• Include 3: (1, 3, [3]).

• Include 1: (2, 4, [3,1]).

• Include 4: the sum becomes 8, so prune and undo 4.

• Exclude 4, then include 2: the sum becomes 6. Record {3,1,2}.

The prompt asks for every solution, so continue. Exclude 3, exclude 1, include 4, and include 2. This records {4,2}. These are exactly the two value-subsets that reach 6.

For this positive, no-zero example, test base cases in this order: if sum == 6, record a copy of picked and return; if i == 4 or sum > 6, return. Otherwise include a[i], recurse, remove it, and recurse on exclusion. Copying is essential. Saving a reference to the shared list would let later undo operations alter an answer already recorded.

3. Turn the trace into code without losing the invariant

Write language-neutral pseudocode before adding language syntax:

search(i, sum, picked):
    if sum == 6: answers.add(copy(picked)); return
    if i == 4 or sum > 6: return
    picked.add(a[i])
    search(i + 1, sum + a[i], picked)
    picked.removeLast()  // restore the caller's state
    search(i + 1, sum, picked)

removeLast() does not delete from the input array. It restores the shared path. Exclusion needs no second undo because it makes no new mutation and receives the state that existed on entry. Every call must return with picked exactly as it found it.

At the successful {3,1,2} leaf, check five facts: the current call has processed 2; sum is 6; a copy is stored; 2 is removed during return; and its caller resumes with {3,1}. The invariant is now observable, not assumed.

4. N-Queens model answer: constraints before recursion

If asked, "How would you solve 4-Queens, and what would you store?", answer by placing one queen per row. At row r, try columns 1..4. Reject a used column, a used r-c diagonal, or a used r+c diagonal. Mark all three, recurse to row r+1, then unmark all three.

For the solution row -> column = [2,4,1,3], the board is:

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

Verify it directly. Columns are {2,4,1,3}. The r-c values are {-1,-2,2,1}, and the r+c values are {3,6,4,7}. None repeats, so no queens share a column or diagonal. The mirrored solution is [3,1,4,2], giving exactly two solutions for N=4.

Generating every board permutation would waste work. Constraint checks happen before recursion, so illegal partial boards produce no descendants. With Boolean arrays or sets, each safety check is O(1). A conventional upper bound is O(N!) search time and O(N) auxiliary recursion and state when board output is excluded.

5. Complexity questions: derive the tree instead of guessing

Subset sum has two choices for each of n undecided values. Without effective pruning,

T(n) = 2T(n-1) + O(1) = O(2^n).

The recursion depth is O(n), while copying each reported subset can cost up to O(n). Pruning may shrink the explored tree for one input, but it does not change the worst-case upper bound.

Permutation generation has a different tree. For ['A','B','C'], the levels offer 3, then 2, then 1 choices, producing ABC, ACB, BAC, BCA, CAB, CBA. Materialising every length-n output costs O(n * n!).

Prefer dynamic programming when different paths repeatedly reach the same (i,sum) state and only existence or a count is required. Memoisation can reuse that result. If every construction must be emitted, its output cost remains. Dynamic Programming Explained: 0/1 Knapsack develops that comparison.

6. Backtracking traps interviewers can expose with one counterexample

Unsafe pruning: With [5,-4,3] and target 4, pruning when the partial sum reaches 5 loses {5,-4,3}, because 5 + (-4) + 3 = 4. Remove the overshoot rule or prove a bound that accounts for the remaining negative and positive values.

Duplicate output: With candidates [1,1,2] and target 3, choosing the 1 at index 0 or index 1 can produce [1,2] twice. If unique value-combinations are required, sort and skip equal choices at the same recursion depth. Do not globally ban the second 1, since another target may require both copies.

Leaked state: In a word-search path, unmark a visited cell when a branch fails. The general invariant is the same: each call returns shared state in its entry condition unless the path has deliberately been committed.

7. How the same core idea changes across interview prompts

For "find one solution", return a Boolean and stop at the first successful leaf. For "return every solution", keep exploring and copy every answer. For "count solutions", return integer counts from children and avoid storing full paths unless required.

Clarify the contract before coding: Are values distinct? Can they be negative or zero? Is input reuse allowed? Are duplicate value-combinations permitted? Does output order matter? What input size must be handled? For [3,1,4,2], changing "use each index once" to "reuse allowed" changes both the state and the search tree.

Use DSA Interview Questions by Pattern: Arrays, Trees, Graphs and Complexity for breadth across arrays, trees, and graphs; this backtracking drill stays on reversible state, safe pruning, and enumeration. The Coding For Placements course covers the wider preparation path.

8. Backtracking practice: recode, trace and log every undo

A strong spoken answer does five things: define the state, list the choices, state the acceptance test, justify every prune, and undo shared mutations. A correct trace on [3,1,4,2] or [2,4,1,3] demonstrates more than memorised syntax.

Recode subset sum from memory and dry-run both solutions. Then solve 4-Queens while logging every (row,column) mark and unmark. Continue with DSA using Java for structured practice, then compare the same state discipline with a BFS visited set.