undoBacktracking

Backtracking: when to spot it, explain it, and practice it

Backtracking is a disciplined way to explore decision trees. Good answers do not just recurse; they define the current path, remaining choices, stopping condition, and pruning opportunities precisely.

Pattern coverage

55+

Best first move

Define what the path means.

Common failure point

Forgetting to undo state and leaking one branch into another.

When this pattern should come to mind

The problem asks for all combinations, permutations, subsets, or valid constructions.

A decision tree exists and each level chooses one item or state.

The result space can be huge, so pruning matters.

Checklist before you code

Define what the path means.

Define what counts as a complete solution.

List which choices remain available at each depth.

Undo every state mutation before the next branch.

The solving flow that works well in interviews

Model the decision tree explicitly.

Choose the next candidate set for the current depth.

Check whether a choice is valid before recursing.

Apply the choice, recurse, then undo it exactly once.

Prune branches early if they can never reach a valid solution.

Common variants

Permutation search

Each level chooses one unused item.

Combination search

Use an index to avoid revisiting earlier choices.

Constraint backtracking

Validity checks and pruning dominate performance.

Template preview

PythonPublic preview

def backtrack(path):
    if complete(path):
        answer.append(path[:])
        return
    for choice in choices(path):
        if not valid(choice, path):
            continue
        path.append(choice)
        backtrack(path)
        path.pop()

Classic problems with useful framing

#78

Subsets

Medium

The simplest possible choice-tree starter.

Return all possible subsets of the given array.

#46

Permutations

Medium

Good for understanding used-state tracking.

Return all permutations of the array.

#39

Combination Sum

Medium

Shows how indexing prevents duplicate work.

Find all combinations that sum to a target, with unlimited reuse of candidates.

#51

N-Queens

Hard

A classic pruning-heavy backtracking question.

Place n queens on an n x n board so that none attack each other.

A more useful problem ladder for practice

This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.

Foundation

#39 Combination Sum

Medium

Find all combinations that sum to a target, with unlimited reuse of candidates.

The same index can be chosen again because repetition is allowed, but earlier indices should not be revisited after moving forward.

Foundation

#46 Permutations

Medium

Return all permutations of the array.

Each recursion level fixes one position in the permutation.

Variant depth

#78 Subsets

Medium

Return all possible subsets of the given array.

Each index creates a binary decision, so the whole answer space is a decision tree of depth n.

Variant depth

#51 N-Queens

Hard

Place n queens on an n x n board so that none attack each other.

At each row you only need to know which columns and diagonals are already occupied.

High-frequency mistakes

warning

Forgetting to undo state and leaking one branch into another.

warning

Not copying the path when saving an answer.

warning

Allowing duplicate combinations due to poor index handling.

warning

Skipping pruning opportunities and timing out.

Recommended practice path

Start with subsets and permutations.

Then solve combination sum and restore IP style problems.

Add board search questions like word search.

Finish with N-Queens and other strong-pruning problems.