Backtracking Interview Questions: One Template for Subsets, Permutations, and N-Queens

Backtracking builds an answer one choice at a time. When the last choice cannot lead to a valid result, it undoes that choice and tries the next one. One template, choose then explore then un-choose, solves subsets, permutations, combination sum, and N-Queens.

One template covers so many questions because they are all the same search. Each asks for every arrangement of choices that satisfies a rule.

This guide shows how to recognize a backtracking question and gives the template in Python. It then applies the template to the four classic problems. After that come pruning, complexity, common bugs, and how to explain the approach in an interview.

How to recognize a backtracking question

Three details in the wording of a question suggest backtracking.

The question asks for all of something. All subsets of a set, all arrangements of a word, or all ways to reach a target sum. A plain loop cannot list arrangements of unknown length, so "all" is the strongest sign.

The question places items under constraints. Eight queens on a board so that none attack each other, or a Sudoku grid with every rule satisfied. Each placement limits the next one, so the code must track what it has already placed.

The input is small. Limits are often about 20 elements for subsets, under 10 for permutations, and a 9 by 9 board for N-Queens. A small limit is a hint that an exponential search is expected.

Exponential means the work roughly doubles, or worse, each time the input grows by one. A count or a best value on a large input usually means dynamic programming instead. The table near the end covers that difference.

The backtracking template

Backtracking uses recursion. Recursion is a function that calls itself on a smaller version of its own problem. Each call extends a shared partial answer, called the path, by one choice.

Each call is one level deeper, and the depth equals the length of the path.

Every backtracking solution repeats three steps at each level.

1. Choose. Add one option to the path.
2. Explore. Call the function again so it extends the longer path.
3. Un-choose. Remove the option, so the next option in the loop starts from the same path.

is_complete and next_choices are the two functions you write for each problem. Every other line stays the same.

results = []

def backtrack(path):
    if is_complete(path):
        results.append(path[:])      # save a copy of the path
        return
    for choice in next_choices(path):
        path.append(choice)          # 1. choose
        backtrack(path)              # 2. explore
        path.pop()                   # 3. un-choose

The copy in the results.append line matters. path is one list that every call shares, so saving the list itself would save something that later calls change.

Subsets: a start index prevents repeats

A subset is any selection of the elements, including none of them and all of them. For n elements there are 2 to the power of n subsets, because each element is either in or out.

The one change to the template is a start index. Each call only considers elements from start onward. So [1, 2] is generated once, and [2, 1] is never tried.

def subsets(nums):
    results = []

    def backtrack(start, path):
        results.append(path[:])          # every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            backtrack(i + 1, path)       # explore from the next index
            path.pop()                   # un-choose

    backtrack(0, [])
    return results

For [1, 2, 3] this returns eight lists, from the empty list to [1, 2, 3]. There is no is_complete check, because every path is a valid answer. So the function saves a copy at the top of every call.

Permutations: a used set or an in-place swap

A permutation is an ordering that uses every element once. For n distinct elements there are n factorial orderings. The count n factorial means n times n minus 1, times n minus 2, and so on down to 1.

Here every element is available at every level, except the ones already in the path. A used set holds the taken elements, so the check is constant time. Constant time means the check costs the same however long the path is.

def permutations(nums):
    results = []
    used = set()

    def backtrack(path):
        if len(path) == len(nums):
            results.append(path[:])
            return
        for x in nums:
            if x in used:
                continue
            used.add(x)                  # choose
            path.append(x)
            backtrack(path)              # explore
            path.pop()                   # un-choose
            used.remove(x)

    backtrack([])
    return results

For [1, 2, 3] this returns six orderings. The other common version swaps nums[i] with nums[depth] in place, calls itself, and swaps back. The swap back is easy to forget, so the used set is the safer choice in an interview.

Combination sum: reuse by not advancing the index

Combination sum asks for every group of numbers from a list that adds up to a target. Each number may be reused any number of times. The order inside a group does not matter, so [2, 2, 3] and [3, 2, 2] count once.

Two changes handle both rules. The recursive call passes i instead of i + 1, which allows the same number again. Sorting first lets the loop stop at the first number larger than the remaining target, since every later number is larger too.

def combination_sum(nums, target):
    results = []
    nums.sort()

    def backtrack(start, path, remaining):
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break                    # sorted, so nothing later fits
            path.append(nums[i])         # choose
            backtrack(i, path, remaining - nums[i])   # same i, so reuse is allowed
            path.pop()                   # un-choose

    backtrack(0, [], target)
    return results

For [2, 3, 6, 7] and a target of 7 this returns [[2, 2, 3], [7]]. The break is the first example of pruning. Pruning means skipping part of the search that cannot produce a valid answer.

N-Queens: one queen per row and three sets

N-Queens asks for n queens on an n by n board with no two in the same row, column, or diagonal. Placing exactly one queen per row satisfies the row rule automatically. So each level of the recursion is one row, and each choice is a column.

Three sets make the other two rules a constant-time check. One set holds the columns already used, and two sets hold the diagonals. Squares on one kind of diagonal share the same row - col, and squares on the other kind share the same row + col.

def n_queens(n):
    results = []
    cols, diag1, diag2 = set(), set(), set()

    def backtrack(row, placement):
        if row == n:
            results.append(placement[:])
            return
        for col in range(n):
            d1, d2 = row - col, row + col
            if col in cols or d1 in diag1 or d2 in diag2:
                continue
            cols.add(col); diag1.add(d1); diag2.add(d2)          # choose
            placement.append(col)
            backtrack(row + 1, placement)                        # explore
            placement.pop()
            cols.remove(col); diag1.remove(d1); diag2.remove(d2) # un-choose
    backtrack(0, [])
    return results

For n of 4 this returns two placements, and for n of 8 it returns 92. Each result lists the column of the queen in each row. So [1, 3, 0, 2] means row 0 has its queen in column 1.

These four problems belong to one pattern. Grokking the Coding Interview teaches the subsets pattern this way, one variation at a time, with worked solutions.

Pruning: how to keep the search small

Pruning means checking a partial answer before exploring it and skipping it when it cannot succeed. Without pruning, backtracking tries every branch. A branch is one sequence of choices from the first level to the last.

Sort first. With the smallest options first, the loop can stop at the first option that is too large. The break in combination sum does that.

Skip duplicates at the same level. Two branches that choose the same value at the same position produce the same answers. Sort first, then skip an element that equals the previous one, unless it is the first one tried on this level.

Here is the subsets function with that one extra check.

def subsets_with_duplicates(nums):
    results = []
    nums.sort()

    def backtrack(start, path):
        results.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                 # same value, same level: skip it
            path.append(nums[i])         # choose
            backtrack(i + 1, path)       # explore
            path.pop()                   # un-choose

    backtrack(0, [])
    return results

For [1, 2, 2] this returns six subsets instead of eight, and none of them repeats. The i > start part is what makes the skip correct. The first 2 on a level is always allowed, and only a second 2 on the same level is skipped.

Stop when the remaining target cannot be met. In combination sum the remaining target only goes down, so the branch ends when the smallest option left is larger than it. The same check applies to any question with a budget, which is a total the answer may not exceed.

Complexity in plain words

Backtracking is exponential, and it is fine to say so in the interview. The useful detail to add is the number of results. The work is at least that number times the cost of copying one result.

For 10 elements, subsets gives 1,024 results and permutations gives 3,628,800. That difference is why permutation questions give smaller inputs.

Space is the depth of the recursion plus the results. The depth is at most n, so the call stack, which is the memory that holds the active calls, stays small. The results list is the large part, and the question requires it.

Common bugs in backtracking code

Saving the path instead of a copy. results.append(path) stores the one shared list, so every later pop changes what was stored. The output becomes a list of empty lists, and the fix is path[:] or list(path).

Forgetting the un-choose step. Without path.pop(), the second option on a level is added after the first instead of replacing it. The code still runs, so the bug is hard to see.

The wrong duplicate skip. Writing i > 0 instead of i > start also skips a repeated value on deeper levels, so subsets like [2, 2] are missing. Skipping without sorting first means equal values are not next to each other, and the check never matches.

Changing shared state without restoring it. Shared state is any variable that every call can see and change, like the used set in permutations. Anything added before the explore step must be removed after it.

Backtracking versus depth-first search versus dynamic programming

All three use recursion, and a common interview question is which one fits. Depth-first search (DFS) visits every node of a graph or tree once, going as deep as it can before returning. Dynamic programming (DP) stores the answer to each subproblem, a smaller version of the same question, so it is computed once.

Backtracking is DFS on a tree of choices that the code builds during the search, rather than on a graph given in the input. The difference is that backtracking undoes each choice, while DFS marks each node as visited and never unmarks it.

For DFS on real trees and graphs, see this guide to tree and graph data structures.

How to explain the approach in the interview

Three sentences cover the approach, and they work for any of the four problems.

1. "I will build the answer one choice at a time, and at each level I try every option that is still valid."
2. "After exploring an option I remove it, so the next option starts from the same partial answer."
3. "When a partial answer cannot succeed I stop early, and that pruning is what keeps the search small."

Then state the number of results and the exponential cost before writing code. More advice on explaining these problems aloud is in tips for solving backtracking problems in interviews.

Backtracking is recursion plus a shared state that every call must restore. Grokking the Art of Recursion teaches recursion from the base case to backtracking problems like these.

Frequently asked questions

What is backtracking in simple terms? Backtracking builds an answer one choice at a time. When the current choice cannot lead to a valid result, it removes that choice and tries the next one. The result is every valid combination, arrangement, or placement.

Is backtracking the same as recursion? No. Recursion is a function calling itself, and backtracking is one use of it. Backtracking adds a shared partial answer that each call extends and then restores before returning.

When should I use backtracking instead of dynamic programming? Use backtracking when the question asks for every solution, or any one solution under constraints, and the input is small. Use dynamic programming when the question asks for a count, a minimum, or a maximum, and the same subproblem repeats. With hundreds of elements, backtracking will not finish in time.

What is the time complexity of backtracking? Exponential in most cases: subsets produce 2 to the power of n results, and permutations produce n factorial. Multiply the number of results by the cost of building one. Pruning lowers the real work but not the worst case.

Which backtracking questions are asked most in interviews? Subsets, permutations, combination sum, and N-Queens are the four to know first. Word Search, Letter Combinations of a Phone Number, Palindrome Partitioning, and Generate Parentheses use the same template. Sudoku Solver is N-Queens with more rules.

Related reading

• What is backtracking in coding?
• Tips for solving backtracking problems in interviews
• What is recursion?
• From recursion to memoization to tabulation: solve the same problem three ways
• Dynamic programming patterns for coding interviews
• LeetCode coding patterns