Backtracking Interview Questions: Choose, Explore, Un-Choose

A prompt that says return all, print every, or find a valid arrangement is asking you to search a decision tree. Backtracking is depth-first search over that tree with one extra move: after you explore a branch, you undo the change that got you there, so the parent sees exactly the state it had before. Choose, explore, un-choose. Subsets, permutations, combination sum, N-Queens, and Sudoku are that same recursion wearing different state and different pruning.

Key Takeaways

• The undo must be the exact inverse of the choose. Two mutations on the way down means two restorations on the way up, in the same call, including the early-return paths.
• Append path[:], never path. Storing the live list is why every result comes back identical or empty.
• Prune inside the loop, against the partial state. Sorting the candidates often turns a continue into a break, which cuts a whole tail of the branch instead of one child.
• Deduplicate by skipping equal siblings after a sort, not by running set() over the finished output.
• Quote branching factor and depth, and count the O(path) copy at every node that emits. Pruning does not change the worst-case bound unless you can bound the pruned tree.

Backtracking is depth-first search plus an undo

Asked at Kickoff — Generate boolean truth table You get a boolean expression as a string: single-letter variables, ! for NOT, adjacency for AND, + for OR, parentheses allowed. Parse it, pull out the distinct variables in alphabetical order, then print one row for every possible assignment of true and false to those variables, along with the value the expression takes. Two variables means four rows; ten means 1024.

Strip the parser away and what remains is the smallest complete backtracking problem there is. Each variable is a node with two children. Set it true, recurse to the next variable, unset it; set it false, recurse, unset it. At depth v you hold a full assignment and evaluate.

def backtrack(state):
    if is_complete(state):
        results.append(snapshot(state))   # a copy, never the live object
        return
    for choice in candidates(state):
        if not is_valid(state, choice):
            continue                      # prune
        apply(state, choice)              # choose
        backtrack(state)                  # explore
        undo(state, choice)               # un-choose

The apply/undo pair is what interviewers actually watch. If apply sets a flag and pushes onto a path, undo clears that flag and pops. Same count, same call, no exceptions.

snapshot carries equal weight. For the truth table the emitted row is a copy of the assignment map; for a path-based problem it is path[:]. Append the live object and you have stored a reference that every later mutation rewrites.

Note the exit from any candidate left? — when the loop runs dry the call returns, which is the only way an incomplete node ever finishes.

For v variables the tree has 2^v leaves and you evaluate an expression of length m at each, so enumeration costs O(2^v · m) with O(v) of stack. Parsing is linear and independent of it.

Once the choice at a node is richer than true or false, the loop changes shape. There are two shapes worth committing to memory.

Subsets carry a start index, permutations carry a used array

Asked at Airbnb — Find Optimal Property Combination (premium) Each rental property has an id, a neighborhood, and a guest capacity. Given a requested neighborhood and a party of groupSize, choose properties in that neighborhood whose capacities together seat the party. The winner is the pick with the smallest total capacity; if two picks tie there, the one using fewer properties wins.

This is subset enumeration with an objective bolted on. Order carries no meaning — {A, B} and {B, A} are one answer — and a start index is what buys you that.

def subsets(nums):
    res, path = [], []

    def dfs(start):
        res.append(path[:])                 # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])            # choose
            dfs(i + 1)                      # explore, never look back
            path.pop()                      # un-choose
    dfs(0)
    return res

dfs(i + 1) is the phrase "never look backwards", and it is what stops (2,1) from appearing after (1,2). Time O(n · 2^n), aux space O(n) excluding the output. There are exactly 2^n calls, one per subset, and every one of them emits.

For the Airbnb version you never materialise all 2^n subsets. You carry a running total capacity and a count, keep the best pair seen, and let the objective prune the branch — which is the next section.

Permutations drop the start index, because order is the answer and every unused element stays live. The bookkeeping moves into a used array.

def permute(nums):
    res, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False
    dfs()
    return res

Time O(n · n!), aux space O(n).

The swap variant, where you exchange nums[i] with nums[start], recurse, then swap back, drops the used array and emits in a different order. It also breaks the duplicate rule below, because it destroys the sorted order that rule depends on. Pick one and be able to say which.

Prune at the node, not at the leaf

Asked at Flexport — Validate and restore IPv4 addresses Three parts that escalate. First, decide whether a dotted string is a legal IPv4 address: four octets, each 0 to 255, no leading zeros, nothing else in the string. Then, given a bare digit string with the dots stripped out, decide whether three dots can be inserted to make it legal. Finally, return every address that insertion can produce, for inputs up to twelve digits.

Generate-then-filter solves part three and loses the offer. There are C(n−1, 3) ways to drop three dots, and checking each afterwards is a filter. Pruning means the illegal branches are never entered at all.

def restore_ip_addresses(s):
    n = len(s)
    res, parts = [], []

    def dfs(start):
        if len(parts) == 4:
            if start == n:
                res.append(".".join(parts))
            return
        remaining = 4 - len(parts)
        left = n - start
        if left < remaining or left > 3 * remaining:
            return                          # can't fill, or can't consume, the rest
        for size in (1, 2, 3):
            if start + size > n:
                break
            seg = s[start:start + size]
            if seg[0] == "0" and size > 1:
                break                       # longer segments also lead with zero
            if int(seg) > 255:
                break                       # value only grows with size
            parts.append(seg)
            dfs(start + size)
            parts.pop()
    dfs(0)
    return res

Three prunes, all of them inside the loop or above it:

The length bound at the top does the heaviest lifting. With remaining segments still to place and left digits in hand, fewer than remaining digits can never fill them and more than 3 * remaining can never be consumed. That check rejects a twenty-digit input at the root rather than at eighty-one leaves.

The leading-zero test uses break, not continue. If a two-digit segment starts with 0, the three-digit one does too, so the rest of the loop is dead.

The 255 test also breaks, because for a fixed start the segment value only climbs as you take more digits. Naming that monotonicity out loud is worth the breath: segment values only grow as I take more digits, so once one exceeds 255 I stop the loop instead of skipping one candidate.

Trace "25525511135". A one-digit first segment "2" dies immediately on the length bound, since ten digits remain for three segments and 3 × 3 = 9. The "25" branch survives one level, then loses two children to the same bound and the third to the 255 break, which rejects "525" before the call is made. Only "255" gets anywhere, and the result is ["255.255.11.135", "255.255.111.35"].

Depth is fixed at four and branching is at most three, so the tree holds at most 3^4 = 81 leaves regardless of input. Under the twelve-digit constraint this is O(1) work with a small constant. The general statement is O(3^k) for k segments, and the useful part of that sentence is that the exponent is the segment count, never the string length.

Skip duplicates at the sibling, not at the end

Asked at Airbnb — Compute minimum-cost service cover Each rental package bundles a set of services at a price, and a listing has services it must offer, matched case-insensitively. Find the cheapest combination of packages covering all of them, and return both the minimum cost and every combination of package indices that reaches it, each written as a strictly increasing index list. If nothing covers the requirements, return −1 and no combinations.

"A strictly increasing list of indices" is the start index restated as an output format. Recursing with dfs(i + 1) emits indices in increasing order by construction, so [0, 2] is generated once and [2, 0] never at all. Passing i instead would let a package be bought twice, which is a different question.

That settles duplicate orderings. Duplicate values are a separate failure, and it appears the moment two candidates are equal.

def combination_sum2(candidates, target):
    candidates.sort()
    res, path = [], []

    def dfs(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue                    # same value, same level: already tried
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            dfs(i + 1, remaining - candidates[i])
            path.pop()
    dfs(0, target)
    return res

i > start is the load-bearing half. Skipping on candidates[i] == candidates[i - 1] alone would also forbid [1, 1], a perfectly legal combination. The rule: an equal value may be reused deeper in the same branch, never retried as a sibling.

Permutations need a different sibling test, since there is no start index to compare against.

def permute_unique(nums):
    nums.sort()
    res, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            if i > 0 and x == nums[i - 1] and not used[i - 1]:
                continue                    # place equal values left to right only
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False
    dfs()
    return res

not used[i - 1] reads backwards to most people. Take it as a canonical-order rule: among equal values, the leftmost copy goes down first. If the previous equal copy is currently unused, placing this one would rebuild a permutation the leftmost copy already produced. Flipping the test to used[i - 1] also deduplicates, pinning the opposite copy; either is defensible as long as you can say which one you fixed.

Collecting everything and calling set(map(tuple, res)) at the end returns correct output. It also costs memory proportional to the un-deduplicated result: for [1,1,1,1,1,1,1,1] that is 40,320 stored permutations for one distinct answer.

One caution specific to the Airbnb version. Two different index sets that reach the same minimum cost are not duplicates of each other — they are both required output. Deduplicate on the index set, never on the cost.

Keep the constraint check O(1)

Asked at Amazon — Validate 9x9 grid in one pass A 9×9 Sudoku board arrives partly filled, blanks marked with .. Decide whether what is already placed breaks a rule: the same digit twice in a row, twice in a column, or twice inside one of the nine 3×3 boxes. The follow-up pins it down — do it in a single scan, and name the data structure.

Amazon is asking for the validator, not the solver. Build it first regardless, because the solver is this function made incremental.

def is_valid_board(board):
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            bit = 1 << (int(ch) - 1)
            b = (r // 3) * 3 + c // 3
            if rows[r] & bit or cols[c] & bit or boxes[b] & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
    return True

Three arrays of nine integers, one bit per digit. rows[r] & bit answers "is this digit already in this row" in a single instruction, and (r // 3) * 3 + c // 3 maps a cell to its box with arithmetic instead of a lookup. O(81) time and O(1) space.

A solver reuses those same three arrays and never rescans anything. The legal digits at a cell are ~(rows[r] | cols[c] | boxes[b]) & 0x1FF; choosing ORs one bit into all three, un-choosing ANDs it out of all three. Three mutations down, three up, one per array.

N-Queens is the identical structure with three sets standing in for three bitmask arrays.

def solve_n_queens(n):
    res = []
    cols, diag, anti = set(), set(), set()
    board = [-1] * n                        # board[r] = column of the queen in row r

    def dfs(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c); diag.add(r - c); anti.add(r + c)
            board[r] = c
            dfs(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)
    dfs(0)
    return res

Recursing by row already encodes one queen per row, so no placement can ever violate that constraint. r - c stays constant along a diagonal and r + c along an anti-diagonal, which is why each check is a set membership instead of a scan across the board.

Video: 6.1 N Queens Problem using Backtracking

On a real Sudoku, ordering beats checking. Picking the empty cell with the fewest legal digits — minimum remaining values — collapses hard boards, and the usual implementation swaps that cell into the current position before recursing.

Two honest notes about that, because both get stated wrongly. The MRV rescan costs O(k) at every node, so the bound is O(k · 9^k) rather than O(9^k). And the swap needs no un-swap: it is a transposition confined to positions ≥ i, and since the next call recomputes MRV across the whole remaining suffix, the set of cells left to fill is identical either way. Running both variants over the same puzzles, the version without the restore produced a valid completion every time; what changed was which valid solution surfaced first on boards with more than one.

That gives you the test for whether any mutation needs an undo. Ask whether the parent's view of the remaining work changes. Marks and placements change it. Reordering a work list does not.

Some marks must never be undone

Asked at Snapchat — Solve Open the Lock BFS A four-wheel lock starts at "0000", and one move turns a single wheel one notch either way, with 9 wrapping round to 0. A list of dead-end combinations jams the lock and can never be entered. Return the fewest moves that reach a target combination, or −1 when it cannot be reached.

Word search shows the undo in its least obvious form, where the mark is written straight into the input.

def exist(board, word):
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])

    def dfs(r, c, k):
        if k == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[k]:
            return False
        ch = board[r][c]
        board[r][c] = "#"                   # choose: mark as on the current path
        found = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1)
                 or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
        board[r][c] = ch                    # un-choose
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Marking in place costs O(1) extra space on top of the O(L) recursion stack for a word of length L. A path-scoped visited set costs the same O(L), because it never holds more than the cells on the current path; it is a fresh visited matrix per starting cell that costs O(m·n). Say which of the two you mean, and flag the mutation before you write into a caller's grid. If mutating is off the table, the set is the right call. The trap left over is choosing a sentinel that could legitimately appear in word.

Now the contrast, because Open the Lock is also a search over states and its mark must never come off.

You want the fewest moves, so this is BFS, and BFS marks a state when it enqueues it and keeps that mark permanently. The reason is worth naming: the first time BFS reaches a state, it has reached it by a shortest path, so arriving there again cannot improve anything. Un-marking would enumerate simple paths through a 10,000-state graph instead of visiting each state once, and it still would not hand you the minimum. Seeding the visited set with the deadends is why they need no special case inside the loop.

The rule generalises cleanly. Undo a mark that means on the current path. Keep a mark that means already reached, and reaching it again cannot help.

When the label says backtracking and the answer is not

Asked at Applied Intuition — Delete duplicate files via DFS Walk a directory tree and group the files whose contents are identical, so the extras can be deleted. The prompt hands you the technique outright — DFS with backtracking — and then asks how you would make the solution run faster.

The prompt says backtracking. The answer is a hash map keyed on file content, with the directory walk as an ordinary traversal. Nothing about the current path constrains the next choice, so there is no state to restore, and the speed follow-up is about hashing on size first and comparing bytes only on collision. Spotting that the label and the technique disagree is part of what is being measured.

Two more questions in the bank read the same way. Find all balanced k in a permutation (Microsoft) puts "permutation" in the title and then explicitly rules out enumerating subarrays; the answer is one sweep tracking the leftmost and rightmost positions of the values 1..k, where k is balanced exactly when those positions span k cells. Count inversions in a permutation (Hudson) asks how many, not which, and a merge sort counts them without ever listing a pair.

Constraints carry the same signal. An n ≤ 20 bound on a subset problem, or n ≤ 10 on a permutation problem, is an invitation to enumerate. n = 10^5 is not, however naturally the problem phrases itself as find all.

And if the question wants how many or what is the best rather than list them all, try DP or greedy first. Counting paths in a grid, word break, and coin change all have exponential backtracking solutions and polynomial-time DP ones, with one caveat worth stating: coin change's O(n · amount) is pseudo-polynomial, since amount is exponential in the number of bits used to write it.

Complexity, stated the way interviewers want it

Problem	Search tree	Time	Aux space (excl. output)	The answer that loses points
Subsets of n	2^n nodes, every node emits	O(n · 2^n)	O(n)	"O(2^n)" — drops the O(n) copy at each node
Permutations of n	n! leaves, ⌊e·n!⌋ nodes	O(n · n!)	O(n)	"O(n!)" — same omission
Combination sum, target T, min candidate m	branching n, depth ≤ T/m	O(n^(T/m))	O(T/m)	"O(2^n)" — n is not the depth here
Restore IPv4, 4 segments	≤ 3^4 leaves, depth fixed at 4	O(1) under the 12-digit cap	O(1)	anything exponential in the string length
N-Queens, n	≤ n! placements, O(1) checks	O(n!) nodes, plus O(n²) to emit each solution	O(n)	"pruning makes it polynomial"
Word search, m×n grid, word length L	3 new directions after the first step	O(m·n·3^L)	O(L)	4^L, or forgetting the O(L) stack
Sudoku, k blanks, MRV rescan	≤ 9 digits per cell	O(k · 9^k)	O(k)	"MRV makes it polynomial"

Enumeration is output-sensitive. If the required output is all n! permutations, nothing beats n!, because the answer itself is that large. This is why "can we memoize this?" is so often the wrong question. Memoisation helps when you need a count or an optimum, not a listing.

Pruning is a constant-factor and average-case win unless you can bound the pruned tree. N-Queens with the three-set check clears n = 12 quickly and its worst-case bound is untouched. Claiming "the pruning makes it O(n²)" without a proof is a red flag. "The bound is unchanged, but the constraint checks kill most of the tree near the root" survives the follow-up.

Recursion depth is real space. Word search costs O(L) of stack, Sudoku O(k), permutations O(n). Space questions are usually a check on whether you count the call stack at all.

FAQ

Is backtracking the same as DFS?

Backtracking is DFS over an implicit decision tree, with state you mutate going down and restore coming back up. Plain DFS on a graph marks nodes visited permanently, because reaching a node a second time adds nothing. Backtracking un-marks, because a cell excluded from one path may belong to another. If there is no state to restore, you are running a traversal.

How do I know a problem wants backtracking?

Two signals arriving together: the output is a list of arrangements rather than a count or an optimum, and the input bound is small, roughly n ≤ 20 for subsets or n ≤ 10 for permutations. A large bound paired with "find all" phrasing usually means there is a structural shortcut, and finding that shortcut is the actual problem.

What is the time complexity of backtracking?

It depends on the tree, not on the technique: roughly branching factor raised to the depth, times the work done at each node. Subsets are O(n · 2^n), permutations O(n · n!), word search O(m·n·3^L). The factor most people drop is copying the current path into the results, which costs O(path length) at every node that emits.

How do I avoid duplicate results without using a set?

Sort the input, then skip equal values appearing as siblings at the same level. For combinations that is if i > start and nums[i] == nums[i-1]: continue. For permutations it is if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue, which forces equal values to be placed left to right. Both suppress the duplicate before it exists rather than after.

When should I use dynamic programming instead of backtracking?

When the question asks for a count or an optimum rather than the full list, and subproblems repeat. Such a search can usually be memoised on its state, collapsing the exponential tree — word break and coin change are the standard examples, though coin change's O(n · amount) is pseudo-polynomial rather than polynomial. If the required output genuinely is every solution, DP cannot rescue you, because the output alone is exponential.

Why do all my results come back identical, or empty?

You appended the live path instead of a copy. res.append(path) stores a reference, so every later mutation rewrites what you already stored, and the finished list mirrors the end state, which is usually empty. Use res.append(path[:]) or list(path).