Take the 24 hours

Home / Blog / Backtracking Interview Template and Talk Track

Backtracking Interview Template and Talk Track

Backtracking Interview Template and Talk Track

Published 2026-10-09 ·

Backtracking interviews are less about clever tricks and more about a stable ritual: choose, explore, unchoose—plus a prune you can say in one sentence. This backtracking interview template talk track gives you that ritual so you do not freeze when the prompt says “return all…” or “place so that…”.

The 10-second classification

Ask:

  1. Am I building a solution incrementally and discarding dead ends?
  2. Do I need all valid configurations, or the first / count / optimal one?
  3. Is the search space permutations, combinations/subsets, or a grid / constraint placement?
  4. What is the prune—when is the partial solution already illegal?

Talk track:

“I’ll use backtracking: maintain a partial path, try each legal next choice, recurse, then undo. I’ll prune as soon as the partial state breaks a constraint.”

If the problem is optimal over overlapping subproblems with optimal substructure, consider DP instead. Say that fork early when relevant.

Universal skeleton

def backtrack(path, state):
    if is_goal(path, state):
        record(path)
        return
    for choice in candidates(path, state):
        if not is_valid(choice, path, state):
            continue
        apply(choice, path, state)      # choose
        backtrack(path, state)          # explore
        undo(choice, path, state)       # unchoose

Narrate the three verbs every time you write them: choose, explore, unchoose. Interviewers listen for undo discipline.

Pattern A: subsets

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

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

    dfs(0)
    return out

Talk track:

“At each index I either have already decided earlier elements; from start onward I choose next elements in order so sets aren’t duplicated.”

Pattern B: combinations (size k)

Same as subsets, but only record when len(path) == k, and stop deepening past k.

def combine(n, k):
    out, path = [], []

    def dfs(start):
        if len(path) == k:
            out.append(path.copy())
            return
        for i in range(start, n + 1):
            # optional prune: not enough numbers left
            need = k - len(path)
            if n - i + 1 < need:
                break
            path.append(i)
            dfs(i + 1)
            path.pop()

    dfs(1)
    return out

State the prune: remaining slots vs remaining numbers.

Pattern C: permutations

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

    def dfs():
        if len(path) == len(nums):
            out.append(path.copy())
            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 out

Talk track:

“Every position can take any unused element. used marks choose/unchoose.”

For duplicates in input, sort and skip nums[i] == nums[i-1] when the previous identical value was not used in this frame—classic duplicate-permutation guard.

Pattern D: grid / constraint (N-Queens flavor)

Partial state includes row, attacked columns, diagonals.

def is_safe(col, diag1, diag2, c, d1, d2):
    return c not in col and d1 not in diag1 and d2 not in diag2

Talk track:

“I’ll place one queen per row. Columns and both diagonal families are sets I update on choose and undo on unchoose.”

Word search on a board is the same family: mark cell visited, recurse 4 directions, unmark.

What to say in the first five minutes

  1. “Output is all solutions / count / any—so I’ll record accordingly.”
  2. “Partial state is …” (path list, used array, sets)
  3. “Branching factor is …; prune when …”
  4. “Time is exponential in the worst case; I’ll prune aggressively.”
  5. Tiny dry-run: subsets of [1,2] or permutations of [1,2] on the pad

Candidates commonly report that interviewers care more about clear undo and prune than about micro-optimizing constant factors. Keep company stories general.

Common bugs

Complexity honesty

Say “O(number of solutions × work per solution)” plus branching discussion. For subsets: O(n · 2^n). For permutations: O(n · n!). Do not claim polynomial time for full enumeration.

Freeze recovery

If you blank:

  1. Write path = [] and def dfs(...):
  2. Write the goal if and append(path.copy())
  3. Write the for-loop with choose / dfs / unchoose empty comments
  4. Fill validity
  5. Only then add prunes

Talk track under freeze:

“I’ll get choose-explore-unchoose correct on a tiny example, then add the prune.”

Soft practice note

Backtracking fails in interviews when narration stalls, not only when code is wrong. If you want timed practice saying the template out loud until it is automatic, Luna Interview is built for calm rehearsal under pressure—practice and composure only, never anything that breaks interview rules.

Day-of checklist

Master the talk track first; the variants are the same skeleton with different candidate generators.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.