What’s the universal three-step skeleton for backtracking?

Category: DSA Patterns

Answer

Pick: choose an option. Constraint: prune if invalid. Unpick: revert the choice before returning. The recursion walks a decision tree and prunes heavily. Memorize the skeleton; the rest is domain-specific.

Concrete examples from the fca project context

Example 1

def backtrack(state, choices): if is_goal(state): record; return; for c in choices(state): apply c; backtrack(state+c, next_choices(state)); undo c.

Example 2

Permutations: state is the partial permutation; choices are the unused elements.

Example 3

N-Queens: choices are columns; constraint prunes attacks; track row by row.

Example 4

Sudoku: choices are digits 1-9 in each cell.

Data flow / flow chart

CHOOSE -> EXPLORE -> UNCHOOSE
   (prune when constraints violated)

Takeaway

Three lines, infinite problems. Always keep the “un-pick” symmetric with “pick” or you’ll leak state.