Backtracking

Try, recurse, undo. The brute-force-with-pruning template that solves permutations, combinations, n-queens, and sudoku.

advancedPractice Full theoryPrereq:Recursion Fundamentals

Start practice Read the theory See all problems

What you'll learn

Recognise 'generate all / find all valid configurations' as backtracking
Write the universal choose / explore / un-choose template
Generate subsets, permutations, and combinations correctly
Handle duplicate elements without producing duplicate results
Prune invalid branches early to cut the search space
Estimate backtracking complexity (it's exponential — know the bound)

When to reach for this

Signals (use it)

"Generate / find ALL ..." subsets, permutations, combinations, partitions
Constraint-satisfaction puzzles: n-queens, sudoku, word search
"How many ways" where you must enumerate (not just count via DP)
Decisions form a tree and invalid partials can be abandoned early

Anti-signals (don't)

Only the COUNT or the OPTIMAL value is needed, with overlapping subproblems → DP
A greedy choice provably works → greedy is far faster
n is large and you'd enumerate exponentially with no pruning → reconsider

Theory & deep dive

Backtracking is systematic brute force: explore every candidate by building a partial solution one choice at a time, and undo the last choice when it leads nowhere. It's depth-first search over the tree of all possible decisions, with the key addition of pruning — abandoning a branch the moment it can't lead to a valid answer.

The whole pattern collapses into three steps repeated recursively: choose (make a move), explore (recurse), un-choose (undo the move so you can try the next one). Get that rhythm in your fingers and every 'generate all ...' problem — subsets, permutations, combinations, partitions — plus constraint puzzles like n-queens and sudoku become the same template with a different 'is this choice valid?' check.

This module gives you the universal template, the choose/explore/unchoose mechanics, how to handle duplicates, and how pruning turns an impossible search into a feasible one.

The big idea in plain words

Backtracking is exploring a maze while dropping breadcrumbs. You walk forward making choices; when you hit a dead end, you walk back to the last fork, pick up your breadcrumb (undo that choice), and try a different door. Try, explore, undo - over and over, until you've covered every path.

Example: all subsets of {1, 2}. Choose 1, and you have {1}; go deeper and add 2 for {1, 2}; then back out. Now skip 1 and choose 2 for {2}. Collecting along the way gives {}, {1}, {1, 2}, {2}. That little 'undo' step is the whole magic - it lets you reuse the same path to try the next option instead of starting over.

The three moves

Every backtracking solution is built from three actions wrapped in recursion.

Step	Action	Code shape
Choose	Add a candidate to the current path	`path.add(x)`
Explore	Recurse with that choice in place	`backtrack(...)`
Un-choose	Remove it so the next candidate is clean	`path.remove(x)`

The un-choose step is what makes it 'backtracking' — you rewind state so the same path object can be reused across all branches. Forget it and your results bleed into each other.

Watch out

The #1 backtracking bug: forgetting to undo the choice (or recording a reference to a mutable path instead of a copy). Add a snapshot to results: res.add(new ArrayList<>(path)), then undo.

The decision tree mental model

Picture the search as a tree: the root is the empty partial solution, each edge is a choice, each leaf is a complete candidate. Backtracking is a DFS over this tree.

Pruning is cutting off a subtree the instant the partial solution is doomed — e.g. in n-queens, the moment two queens attack each other, you don't explore that branch's millions of leaves. Good pruning is the difference between 'runs instantly' and 'never finishes'.

The universal template

Memorise this skeleton; every problem just fills in 'is this a complete solution?', 'what are the candidate choices?', and 'is this choice valid?'.

Java· Subsets — the canonical template

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));      // record a snapshot
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);               // choose
        backtrack(nums, i + 1, path, res); // explore (i+1: no reuse)
        path.remove(path.size() - 1);    // un-choose
    }
}

Subsets vs permutations vs combinations

These three differ only in how the loop advances and whether order matters.

Problem	Order matters?	Reuse elements?	Key loop detail
Subsets	no	no	recurse with `i+1`, record every node
Combinations (k of n)	no	no	recurse with `i+1`, record at depth k
Permutations	yes	no	loop from 0, track a `used[]` set
Combination sum (reuse)	no	yes	recurse with `i` (not i+1) to reuse

The start index vs used[] array distinction is the crux: a start index prevents revisiting earlier elements (so order doesn't matter); a used[] set lets you pick any unused element (so order does).

Handling duplicates

When the input has duplicate values, you'll generate duplicate results unless you guard against it. The fix: sort the input first, then in the loop, skip a candidate if it equals the previous one and the previous one wasn't used at this level. This keeps one canonical ordering of equal elements and eliminates repeats without a hash set.

Python· Subsets with duplicates

def subsets_with_dup(nums):
    nums.sort()                       # group equal values
    res, path = [], []
    def backtrack(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue              # skip duplicate at this level
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return res

How to talk about this in the interview

“Frame it as constrained brute force: "I need to enumerate all valid configurations, so I'll backtrack — choose a candidate, recurse, then undo so I can try the next. I'll prune branches that already violate the constraints." Be explicit about the snapshot/undo pair, because that's where bugs live. Acknowledge the complexity honestly: "This is exponential — O(2^n) for subsets, O(n!) for permutations — which is expected since the output itself is that large; pruning keeps it tractable for the given constraints."”

Common mistakes

–Forgetting to un-choose (undo) the last move, corrupting sibling branches
–Storing a reference to the mutable `path` instead of a copy/snapshot in results
–Using a `start` index when order matters (permutations need a `used[]` set)
–Not sorting before the duplicate-skip check, so duplicates slip through
–Recursing with `i` instead of `i+1` when elements can't be reused (or vice versa)
–Missing pruning, so the search explores doomed branches and times out

Complexity summary

Backtracking is exponential by nature: subsets O(2^n), permutations O(n!·n), combinations O(C(n,k)·k). Space is O(n) for the recursion depth and current path (excluding the output). Pruning reduces the constant/branching factor but not the worst-case class.

Practice problems

13 total