Backtracking — Tech Epitome

Backtracking

Build a candidate incrementally, and undo the moment it cannot work.

Hard9 problems1 chapter

How do I recognise this pattern?

The problem asks for all permutations, combinations, subsets, or arrangements.
You must find every solution, not merely count or optimise.
Choices are made in sequence and each constrains the next.
The input is small — often n ≤ 20 — because the answer space is exponential.
Puzzle framing: placing pieces, filling a grid, partitioning a string.

When it is the wrong tool

Only the count or the optimum is needed and subproblems repeat — that is dynamic programming.
There is a direct constructive rule, making the search unnecessary.
The input is large. Backtracking over n = 1000 will not finish regardless of pruning.

What is it?

Explore a decision tree depth-first, extending a partial solution one choice at a time. When a partial solution cannot possibly be completed, abandon it and undo the last choice rather than continuing. The undo step is what makes this different from plain recursion, and pruning is what makes it tractable.

The core idea

Choose, explore, un-choose. The un-choose is not optional bookkeeping — it is what lets one mutable buffer serve the entire tree instead of copying state at every node.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1def subsets(nums):2    results = []3    current = []4 5    def explore(start):6        # Every node of the tree is a valid subset, so record on entry.7        results.append(current[:])   # copy: 'current' keeps mutating8 9        for i in range(start, len(nums)):10            current.append(nums[i])   # choose11            explore(i + 1)            # explore12            current.pop()             # un-choose13 14    explore(0)15    return results16 17 18def permutations(nums):19    results = []20    used = [False] * len(nums)21    current = []22 23    def explore():24        if len(current) == len(nums):25            results.append(current[:])26            return27 28        for i in range(len(nums)):29            if used[i]:30                continue31            used[i] = True32            current.append(nums[i])33            explore()34            current.pop()35            used[i] = False   # both pieces of state must be undone36 37    explore()38    return results

Common mistakes

Appending `current` rather than a copy, so every result aliases the same list and ends up empty.
Undoing only part of the state — popping the value but forgetting to clear the `used` flag.
Passing `i + 1` versus `start` incorrectly, which is the difference between combinations and permutations.
Skipping pruning entirely, turning a feasible search into one that never terminates.

Problems using Backtracking

Problem	Difficulty	Role
Generate Balanced Groupings#49	Medium	Primary
Count Subsets With a Target Sum#50	Medium	Primary
Keypad Spellings#131	Medium	Primary