Learn interview-prep-45

Backtracking

Browsing without an account — progress is saved in this browser only.Sign in to save it

Backtracking

Reading135 min

Picture trying on every combination of shirt and pants in your closet, but the moment you notice a shirt clashes with a color of pants, you skip trying it with any other pants and move straight to the next shirt. That's backtracking: explore a choice, and the moment it stops making sense, undo it and try the next one instead of blindly finishing a doomed combination. It's how you list every valid configuration of something (subsets, permutations, combinations) without brute-forcing every possibility blindly. It's one of the highest-frequency interview patterns, because the code shape stays nearly identical across problems, and interviewers use small twists, like duplicates, reusing an item, or a fixed length, to check whether you actually understand the recursion tree or just memorized one template.

Choice, constraints, goal framework

Every backtracking problem breaks down into three questions:

Choice: at this point in the recursion, what options can I pick from next?
Constraints: which of those options are actually valid given what I've already picked?
Goal: when do I have a complete, valid answer worth recording?

Python

def backtrack(path, choices):
    if is_goal(path):           # goal check
        record(path)
        return
    for choice in choices:      # choice enumeration
        if not is_valid(choice, path):  # constraint check
            continue
        path.append(choice)
        backtrack(path, next_choices(choices, choice))
        path.pop()               # undo — this is the "back" in backtracking

The path.pop() right after the recursive call is the entire idea in one line: try a choice, explore everything downstream of it, then undo it so the next sibling choice starts from a clean slate. Forgetting that undo is the single most common backtracking bug, and it silently corrupts every branch that comes after it.

Remember: every backtracking loop asks the same three questions: what can I pick, is it valid, am I done? And it always undoes a choice before trying the next one.

Pruning optimization

Backtracking without pruning is just exhaustive search with extra bookkeeping. Pruning means noticing that a partial path can never lead to a valid goal, and abandoning it right away instead of recursing all the way down to find that out later.

Python

# Without pruning: recurse fully, check validity only at leaves — wasteful
# With pruning: check validity at every step, bail out early

def backtrack(path, remaining_sum, candidates, start):
    if remaining_sum < 0:          # prune: overshot, no point continuing
        return
    if remaining_sum == 0:
        record(path)
        return
    for i in range(start, len(candidates)):
        if candidates[i] > remaining_sum:   # prune: sorted array, rest are bigger too
            break
        path.append(candidates[i])
        backtrack(path, remaining_sum - candidates[i], candidates, i)
        path.pop()

Sorting the input first often makes pruning possible where it otherwise wouldn't be, like the break above: once one candidate is too large, every candidate after it is too, since the array is sorted. That turns a correctness check, skipping invalid branches, into a real performance win.

Remember: don't wait until a leaf to discover a branch was hopeless. Check as early as possible and bail out before wasting more recursion on it.

Combination vs permutation

This distinction decides where your loop starts each recursive call, and it's the detail interviewers watch closely.

Combinations / subsets (order doesn't matter): each recursive call starts its loop from start (or start + 1), never revisiting earlier indices. [1,2] and [2,1] count as the same combination, so you never generate both.
Permutations (order matters): each recursive call loops over all indices not yet used, tracked with a used set or by swapping. [1,2] and [2,1] are different permutations, so both must be generated.

Python

# Combinations: loop starts at `start`, moves forward only
for i in range(start, len(nums)):
    ...
    backtrack(i + 1)   # next call starts after i

# Permutations: loop scans everything, skip what's used
for i in range(len(nums)):
    if used[i]:
        continue
    ...
    backtrack()   # next call scans from 0 again

Mixing these up is the classic bug. A start index used for a permutation problem silently produces only results in sorted order; a full scan used for a combination problem produces duplicates.

Remember: combinations move the starting point forward and never look back. Permutations scan everything every time and just skip what's already used.

Subsets

LeetCode 78 · Subsets · Backtracking · Generate all subsets

Intuition: Every element is either "in" or "out" of a given subset. Backtracking naturally lists all of them by recording the current path at every recursive call, not just at the leaves, since every prefix is itself a valid subset.

Approach: Standard combination-style loop starting at start, recording path at every node of the recursion tree, not only at the base case.

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    path = []

    def backtrack(start: int) -> None:
        result.append(path[:])          # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Complexity: O(n * 2^n) time (2^n subsets, O(n) to copy each), O(n) recursion depth excluding the output.

Common mistakes: appending path directly instead of path[:], which stores a reference that later gets mutated and corrupts every subset already recorded; forgetting that every recursive call, not only the leaves, produces a valid answer here.

Remember: Subsets records an answer at every single node, not just at the leaves, because every prefix is already a valid subset.

Subsets II

LeetCode 90 · Subsets II · Backtracking · Handle duplicates

Intuition: The input may have duplicate values. Sort first, then at each recursion level, skip a candidate if it's equal to the previous candidate at that same level, not globally. That previous one already covered every subset this one would produce.

Approach: Sort nums. In the loop, skip nums[i] when i > start and nums[i] == nums[i-1].

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    path = []

    def backtrack(start: int) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # skip duplicate at this recursion level
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Complexity: O(n * 2^n) time worst case, O(n) recursion depth.

Common mistakes: skipping duplicates with a global seen set instead of the i > start same-level check. A global set wrongly blocks valid subsets that reuse a value at a different branch of the tree. Also, forgetting to sort first, which the same-level dedup depends on completely.

Remember: skip a duplicate only if it's a repeat at the SAME level as the one right before it, not a repeat anywhere in the whole array.

Combination Sum

LeetCode 39 · Combination Sum · Backtracking · Unbounded knapsack

Intuition: The same number can be reused as many times as needed, so the recursive call passes i (not i + 1), to allow re-picking the current candidate.

Approach: Sort candidates for pruning. Track the remaining target, subtract as you go, prune when remaining < 0, record when remaining == 0.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result = []
    path = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # sorted, so nothing further can work either
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])  # i, not i+1: reuse allowed
            path.pop()

    backtrack(0, target)
    return result

Complexity: O(n^(target/min_candidate)) time worst case (exponential, bounded by the target), O(target / min_candidate) recursion depth.

Common mistakes: passing i + 1 instead of i, the classic bug that silently turns "unbounded reuse" into "each number used at most once," which is actually a different problem (Combination Sum II). Also, forgetting to sort before relying on break as a pruning strategy.

Remember: passing i instead of i + 1 into the recursive call is what allows reusing the same number. That single character is the whole difference from "use once."

Permutations

LeetCode 46 · Permutations · Backtracking · Generate permutations

Intuition: Unlike combinations, order matters here, and every index can appear in every position, so the loop scans the full array each time, skipping only what's already placed in the current path.

Approach: Track a used boolean array (or set) instead of a start index, since permutations don't have an "already passed this index" idea; they have "already placed this value."

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

Complexity: O(n * n!) time (n! permutations, O(n) to copy each), O(n) space for used plus recursion depth.

Common mistakes: using a start index like a combination problem, which produces only 1 ordering instead of n!. Also, forgetting to reset used[i] = False on backtrack, which corrupts sibling branches.

Remember: permutations need a used set, not a start index, because any leftover value can go in any leftover position.

Notice where each problem records its answer follows directly from its own goal condition: Subsets records at every node because every prefix is valid, Combination Sum records only when remaining == 0, and Permutations records only once path reaches full length. Get the goal condition right, and the recording point falls out for free.