LiveCodingInterview.com
← Articles

Backtracking Algorithm: One Template, Four Real Problems

A backtracking algorithm builds a solution one choice at a time, checks after every choice whether the partial answer can still work, and undoes the last choice the moment it can't. That single move, adding a candidate to a path, recursing forward, then removing it again before trying the next option, is the entire technique, and almost everything else is bookkeeping around it. It shows up constantly in interviews because "find every combination" or "find any valid arrangement" problems, subsets, permutations, N-Queens, Sudoku, word search, all reduce to that same recursive shape once you recognize it. This piece gives you one reusable template, walks it through four real interview problems with their actual time complexity, and covers the mistakes that quietly cost candidates the round even when their logic was right.

What Is a Backtracking Algorithm?

A backtracking algorithm is a way of searching through every possible sequence of choices for a problem by building one candidate path at a time and abandoning a path as soon as it can no longer lead to a valid answer. Picture it as a depth-first search over a tree of decisions, where each node is a partial solution and each edge is one more choice added to it. You walk down a branch, and the instant you can prove that branch is dead, you climb back up to the last decision point and try a different branch instead. That climbing back up is the "backtrack" the technique is named for, and it's what separates backtracking from a plain brute-force search that tries every path to the end regardless of whether it's obviously wrong partway through.

The tree this search moves through is usually called a state space tree, and its shape tells you almost everything about how expensive the algorithm will be. A problem with b choices at every level and a solution length of d ends up with a tree of roughly b to the power of d leaves in the worst case, and backtracking's entire value proposition is that good pruning, the "abandon early" check, cuts huge sections of that tree before you ever visit them. Without pruning, backtracking degrades into brute force with extra bookkeeping, which is exactly why interviewers care whether you can explain your pruning condition, not just your recursion.

How Do You Recognize a Backtracking Problem?

You can recognize a backtracking problem from a small set of signals in the wording before you write any code, and interviewers tend to reuse the same phrasings often enough that spotting them turns a cold problem into a familiar shape within the first thirty seconds.

Watch for these signals together, since any single one alone can point to a different technique:

  • the problem asks for every valid combination, subset, permutation, or arrangement, not just one
  • a partial answer can be checked for validity before it's complete
  • the input size is small, usually n of 20 or fewer, a strong hint an exponential search is intended
  • there's a natural notion of undo, where adding an element to a path and later removing it leaves the rest of the state unchanged
  • a single greedy pass provably doesn't work, since an early decision can invalidate a solution that only becomes visible several choices later

Small input size is the fastest gut check available mid-interview. A constraint like n of 12 or fewer tells you an exponential-time search is expected. Seeing n up to 100,000 alongside "every combination" should make you suspicious the question wants a formula or a DP table, not a full enumeration.

What Is a Reusable Backtracking Template?

A reusable backtracking template has three moves that repeat for every problem: choose a candidate, explore what happens after that choice, and un-choose it before trying the next candidate. Nearly every backtracking solution you'll write in an interview is this same shape with a different validity check and a different definition of "done" plugged in.

def backtrack(path, options):
    if is_solution(path):
        record(path)
        return

    for option in options:
        if not is_valid(path, option):
            continue
        path.append(option)                              # choose
        backtrack(path, next_options(options, option))    # explore
        path.pop()                                        # un-choose

Four things change from problem to problem: what counts as a finished solution, what makes a candidate invalid, what the next round of options looks like, and whether you record every valid path or stop at the first one. Everything else, the loop, the append, the recursive call, and the pop right after it, stays fixed. Once that shape is automatic, a new backtracking problem becomes an exercise in filling in four blanks instead of designing a search from scratch, and that's the actual skill an interviewer is checking for.

How Does the Template Solve Subsets, Permutations, and N-Queens?

The template above solves four of the most commonly asked backtracking problems with almost no changes beyond the validity check and the stopping condition, and working through all four side by side is the fastest way to see the pattern stop feeling abstract.

Subsets

Subsets asks for every possible subset of a list of numbers, including the empty set and the full list itself. Every element is either in the current subset or it isn't, so the choice at each step is simply which remaining element to add next, and every partial path is already a valid answer worth recording.

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

The start index is what keeps this from generating the same subset twice in a different order. Passing i + 1 forward means every recursive call only considers elements after the one just chosen, so [1, 2] gets built once instead of also as [2, 1].

Permutations

Permutations asks for every possible ordering of a list, which means every element must appear in every path exactly once, unlike subsets where an element can be left out. That's why permutations needs a used array: without tracking which elements are already in the current path, nothing stops the recursion from placing the same element twice.

def permutations(nums):
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        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

Notice the stopping condition changed from always recording, in subsets, to only recording once the path reaches full length. That single line is usually the difference between a subsets solution and a permutations solution once the rest of the template is in place.

N-Queens

N-Queens asks you to place n queens on an n by n board so that no two queens share a row, column, or diagonal, and it's the problem most likely to appear when an interviewer wants to see real pruning rather than enumeration. The choice at each step is which column to place a queen in for the current row, and the validity check, no shared column or diagonal, keeps the search from wasting time on boards that are already broken.

def solve_n_queens(n):
    solutions = []
    cols, diag1, diag2 = set(), set(), set()
    path = []

    def backtrack(row):
        if row == n:
            solutions.append(path[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            path.append(col)
            backtrack(row + 1)
            path.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return solutions

The two diagonal sets are the part candidates usually miss on a first attempt. Every cell on a downward diagonal shares the value row minus col, and every cell on an upward diagonal shares row plus col, so tracking both sets turns a linear check into a constant-time lookup.

Combination Sum

Combination Sum asks for every combination of numbers from a list that adds up to a target, where the same number can be reused. That reuse rule is what separates it from subsets, and it shows up in the code as one detail: the recursive call passes i forward instead of i + 1, so the current index stays eligible for the next choice.

def combination_sum(candidates, target):
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return result

The remaining less than zero check is the pruning step, and it does real work: without it, the search keeps adding candidates well past the target before noticing the sum was already too large.

What Is the Time Complexity of Backtracking?

The time complexity of a backtracking algorithm is roughly the number of branches raised to the depth of the search tree, though the exact figure depends on how many valid choices remain at each step and how aggressively you prune invalid ones. That's a wide range in practice, from the exponential subsets of a set to the factorial orderings of a permutation, so it's worth working out the number for the problem in front of you rather than saying "exponential" and stopping there.

| Problem | Time complexity | Space complexity | | --- | --- | --- | | Subsets | O(n times 2^n) | O(n) recursion depth, O(n times 2^n) output | | Permutations | O(n times n!) | O(n) recursion depth, O(n times n!) output | | N-Queens | O(n!) worst case, cut sharply by pruning | O(n) recursion depth | | Combination Sum | O(2^target) worst case | O(target) recursion depth |

Pruning is the variable an interviewer actually wants you to reason about out loud, since the raw exponential bound rarely tells the whole story. N-Queens has a worst-case bound in the hundreds of thousands for a modest board size, but the column and diagonal checks eliminate most branches within the first few rows, which is why an 8 by 8 board solves almost instantly despite that loose bound. Naming that gap is usually worth more in an interview than getting the exact Big O notation right on the first try.

Backtracking vs Recursion vs Dynamic Programming: What's the Real Difference?

Backtracking and dynamic programming are both built on recursion, but they solve different shapes of problem, and mixing them up is a common way candidates lose time on an interview they were otherwise handling well. Recursion is just a function calling itself, a tool. Backtracking is a specific way of using that tool to search a space of candidate solutions and abandon paths early. Dynamic programming is a different way of using the same tool, one that caches the answer to each distinct subproblem so it never gets recomputed.

The real test is whether the same subproblem shows up more than once as the recursion unfolds. A DP problem like computing a Fibonacci sequence or filling a knapsack revisits the same smaller input repeatedly, which is what makes caching pay off. A backtracking problem like generating permutations almost never revisits the same partial path twice, since the path itself, not just an index or a running sum, is the state. Try to memoize a permutations solution and the cache never hits, because the key, the full path built so far, is different on nearly every call.

That distinction is the fastest way to tell the two apart when a problem's phrasing is ambiguous. A count or an optimal value with recurring smaller inputs points to dynamic programming. Every valid arrangement enumerated, with a state that can't shrink below the whole path so far, points to backtracking instead.

What Mistakes Cost Candidates Points on Backtracking Problems?

Two mistakes account for most of the points lost on backtracking problems, and neither one is about knowing the algorithm; both are about executing it under pressure.

The first is forgetting to undo a choice before trying the next one. It's easy to remember the append call and forget the matching pop, especially once the validity check gets more complicated than a single line, and the bug it produces is nasty because it doesn't crash. The code runs and returns results, and those results are simply wrong, since every later branch is quietly carrying leftover state from a branch that should have been abandoned. Reading your own template out loud, choose, explore, un-choose, right before you start coding catches this before it ships.

The second is weak or missing pruning, where a candidate writes a correct brute-force search and never adds the early-exit check that would make it fast enough to matter. An interviewer watching you solve Combination Sum without the remaining-less-than-zero check, or N-Queens without the diagonal sets, sees working logic but no sense of where the real cost lives. Naming the pruning opportunity out loud, even before you've finished coding it, signals that you understand why the naive version is slow and specifically what fixes it.

How Do You Talk Through a Backtracking Solution in an Interview?

Talk through a backtracking solution by naming the three template moves out loud as you write each one, since an interviewer who can't hear your reasoning has only the final code to grade, and code alone rarely shows why a particular pruning check exists. Say what counts as a finished path before you write the base case, say what makes a candidate invalid before you write the check, and say why you're popping an element right after you push it, even though that line looks obvious once it's already on the screen.

Complexity deserves the same treatment: state the loose worst-case bound first, then name what your pruning does to that bound in practice, the way the diagonal check does for N-Queens. That two-part answer reads as far more senior than a single Big O expression, the same habit our breakdown of interview time complexity covers for every other algorithm family.

If you get the recursion wrong on a first attempt, say so and trace through a small input by hand rather than staring at the screen. Walking a three-element list through your own subsets code out loud, watching the path grow and shrink, catches most bugs faster than silent debugging and keeps the interviewer following your reasoning.

Where to Practice Backtracking Next

Subsets, permutations, N-Queens, and Combination Sum cover the core template, but the fastest way to make it automatic is working through more problems that use the same three moves with a different validity check bolted on: word search, palindrome partitioning, and Sudoku solver are the natural next step once these four feel routine. Our curated question bank pulls backtracking problems from real onsite reports rather than an unfiltered public archive, so the versions you practice match what loops are actually asking instead of problems that stopped showing up years ago.

Pair this template with pattern recognition across the rest of the coding round so backtracking becomes one identifiable shape among several, not an isolated trick you only remember when a problem looks like one you've already seen. Spotting the shape in the first thirty seconds buys you the time to write the rest of it calmly. If your loop also includes a design round, our 45-minute framework covers the same structured reasoning for that stage.

Frequently Asked Questions

Is backtracking the same as recursion?

No, recursion is a function calling itself, the underlying tool. Backtracking is one specific way of using that tool: building a partial solution, checking it, and undoing the last step when a branch fails. Plenty of recursive functions, computing a factorial for instance, aren't backtracking at all, since there's nothing to undo and nothing being searched.

What is the time complexity of a backtracking algorithm?

It depends on the number of choices at each step and the depth of the search, generally expressed as branches raised to the depth. Subsets run in O(n times 2^n), permutations in O(n times n!), and N-Queens has a loose bound of n! that real pruning cuts far smaller in practice. There's no single answer across every backtracking problem, so work out the branching factor and depth for the specific one in front of you.

When should you use backtracking instead of dynamic programming?

Use backtracking when the problem wants every valid arrangement enumerated and the state genuinely can't be reduced to something smaller than the whole path built so far. Reach for dynamic programming instead when the question wants a count or an optimal value and the same smaller subproblem keeps recurring, since that repetition is what makes caching pay off in a way it never does for backtracking's mostly unique paths.

What are the most common backtracking interview problems?

Subsets, permutations, combination sum, N-Queens, word search, and Sudoku solver cover most of what shows up in real loops. All six follow the same choose, explore, un-choose template with a different validity check and stopping condition, so getting comfortable with the template matters more than memorizing any one of them individually.

How do you optimize a slow backtracking solution?

Add or tighten the pruning check that rejects an invalid partial path as early as possible, rather than waiting until a full candidate is built to discover it was invalid. Sorting the input first often helps too, since it lets a check like the remaining-less-than-zero one in Combination Sum exit a loop early.

Do interviewers expect an optimal backtracking solution on the first attempt?

Rarely, most interviewers are satisfied with a correct brute-force backtracking solution that explores every valid path, followed by a clear explanation of where pruning would cut the search down and why. Naming the optimization out loud, even without fully coding it, usually counts for as much as writing it does.