Backtracking Interview Problems: Subsets, Permutations, N-Queens & Sudoku

Backtracking problems have a reputation for being tricky, but they are some of the most formulaic questions in coding interviews. Once you see that subsets, permutations, combination sum, palindrome partitioning, word search, N-Queens and Sudoku are the same algorithm with different "choices" and "constraints", you can write any of them in 15 minutes. The difficulty is in the details: copying the path, undoing state, and skipping duplicates correctly.

If recursion itself still feels uncomfortable, read recursion for beginners first. This guide assumes you can trace a recursive call.

What Backtracking Is: Searching a Decision Tree

Picture every solution as a sequence of decisions. For subsets of [1, 2, 3], the decisions are "include 1?", "include 2?", "include 3?". Lay them out as a tree: the root is the empty decision list, each edge is one decision, and each leaf is a complete candidate. Backtracking walks this tree depth-first, keeping a single mutable path that represents the decisions made so far.

Two things make it smarter than brute force:

1. Shared state with undo. Instead of copying the path into every recursive call, you append before recursing and remove after. One list serves the whole search.
2. Pruning. If a partial path already violates a constraint (two queens attack each other, the running sum exceeds the target), you return immediately and skip the entire subtree below it.

The Universal Backtracking Template

def backtrack(state, choices, path, results):
    if is_complete(state):
        results.append(path[:])            # COPY the path
        return                             # (omit return if every node is an answer)
    for choice in choices(state):
        if not is_valid(state, choice):
            continue                       # prune
        make(choice, state, path)          # choose
        backtrack(next_state, choices, path, results)   # explore
        undo(choice, state, path)          # un-choose

void backtrack(int[] nums, int start, Deque<Integer> path, List<List<Integer>> res) {
    if (isComplete(path)) {
        res.add(new ArrayList<>(path));     // copy, never add `path` itself
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if (!isValid(nums[i], path)) continue;
        path.addLast(nums[i]);              // choose
        backtrack(nums, i + 1, path, res);  // explore
        path.removeLast();                  // un-choose
    }
}

For each new problem, answer four questions before writing code:

Subsets (LeetCode 78): Every Node Is an Answer

Use a start index so each element is considered only after the previous chosen one. That prevents [2, 1] after [1, 2]. Because every partial path is itself a valid subset, record it at every node, not just at leaves.

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, 0, new ArrayList<>(), res);
    return res;
}

private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));             // record every node
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        dfs(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void dfs(const vector<int>& nums, int start) {
        res.push_back(path);                    // push_back copies
        for (int i = start; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
};

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

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

    dfs(0)
    return res

Dry run for [1, 2, 3] showing the recursion tree and the order results are recorded:

Bitmask alternative: each integer from 0 to 2ⁿ−1 encodes a subset (bit i set means include nums[i]). It is iterative and handy when n ≤ 20; see bit manipulation tricks. Interviewers like hearing both approaches.

Permutations (LeetCode 46): Track What Is Used

Order matters now, so a start index is wrong: after choosing 2, you must still be able to choose 1. Instead, keep a used boolean array, and record only when the path has length n.

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

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

    dfs()
    return res

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    permute(nums, 0, res);
    return res;
}

private void permute(int[] a, int k, List<List<Integer>> res) {
    if (k == a.length) {
        List<Integer> p = new ArrayList<>();
        for (int x : a) p.add(x);
        res.add(p);
        return;
    }
    for (int i = k; i < a.length; i++) {
        swap(a, k, i);                  // put a[i] in position k
        permute(a, k + 1, res);
        swap(a, k, i);                  // undo
    }
}

private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

The swap version treats positions 0..k−1 as fixed and positions k..n−1 as the pool of unused elements. It uses O(n) recursion space and no extra arrays. Both produce n! permutations in O(n · n!) total time.

Combinations and Combination Sum: Record at the Target

Combinations (77): choose k of n

Same as subsets, but record only when len(path) == k. Prune with arithmetic: if the remaining numbers cannot fill the path (n - i + 1 < k - len(path)), stop the loop.

Combination Sum (39): unlimited reuse

Find all combinations of candidates that sum to a target, where each candidate may be used any number of times. The only change from subsets: recurse with i (not i + 1) so the same element can be chosen again. Sorting enables a break as soon as a candidate exceeds the remaining target.

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void dfs(const vector<int>& c, int start, int remain) {
        if (remain == 0) { res.push_back(path); return; }
        for (int i = start; i < (int)c.size(); i++) {
            if (c[i] > remain) break;           // sorted: all later ones are bigger too
            path.push_back(c[i]);
            dfs(c, i, remain - c[i]);           // i, not i + 1: reuse allowed
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return res;
    }
};

Dry run with candidates [2, 3, 6, 7], target 7: path [2] (remain 5) → [2,2] (3) → [2,2,2] (1) → next 2 > 1, break. Back to [2,2], try 3: remain 0, record [2,2,3]. Back to [2], try 3: [2,3] remain 2, next 3 > 2 break; try 6 > 5 break. Back to root, [3] remain 4 → [3,3] remain 1, break... [6] remain 1, break. [7] remain 0: record [7]. Results: [2,2,3] and [7].

The break is the pruning that matters: without sorting you would need continue and would examine every candidate at every node.

Handling Duplicates: Subsets II, Combination Sum II, Permutations II

When the input has repeated values, the naive template produces repeated results. Deduplicating at the end with a set works but wastes time generating them. The right technique avoids generating duplicate branches.

Same-level skip (Subsets II, Combination Sum II)

Sort the input. In the loop, skip nums[i] if i > start and nums[i] == nums[i-1]. Meaning: at this level of the tree, we already started a branch with this value; starting another identical branch would generate the same subtrees.

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

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

    dfs(0, target)
    return res

Note i > start, not i > 0. With i > 0, you would forbid using the second 1 in [1, 1, 6] even as the second element of a path, losing valid answers like [1, 1, 6] for target 8.

Permutations II (47)

Sort, use the used array, and skip nums[i] when nums[i] == nums[i-1] and !used[i-1]. This forces identical values to be placed in their original relative order, so each distinct permutation is generated exactly once.

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.add(nums[i]);
        dfs(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Partitioning Strings: Palindrome Partitioning and Restore IP Addresses

In partition problems, the choice at each step is "where does the next piece end?". From index start, try every end e; if s[start..e] is valid, recurse from e + 1. Complete when start == len(s).

def partition(s):
    n = len(s)
    # precompute is_pal[i][j] in O(n^2) so each check is O(1)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])
    res, path = [], []

    def dfs(start):
        if start == n:
            res.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end + 1])
                dfs(end + 1)
                path.pop()

    dfs(0)
    return res

Precomputing palindromes with DP is the optimisation interviewers look for. The worst case (a string of identical letters) still has 2ⁿ⁻¹ partitions, so time is O(n · 2ⁿ). Restore IP Addresses (93) is the same pattern with pieces of length 1–3, value ≤ 255, no leading zeros, and exactly four pieces, a strong pruning bound: if the remaining characters exceed 3 × remaining pieces, stop.

N-Queens (51): Constraint Backtracking with O(1) Checks

Place n queens on an n × n board so none attack each other. Since each row holds exactly one queen, the decision at row r is which column to use. A placement (r, c) is safe if column c is free, the diagonal r − c is free and the anti-diagonal r + c is free.

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queenCol = new int[n];
    boolean[] cols = new boolean[n], diag = new boolean[2 * n - 1], anti = new boolean[2 * n - 1];
    place(0, n, queenCol, cols, diag, anti, res);
    return res;
}

private void place(int r, int n, int[] qc, boolean[] cols, boolean[] diag,
                   boolean[] anti, List<List<String>> res) {
    if (r == n) {
        List<String> board = new ArrayList<>();
        for (int row = 0; row < n; row++) {
            char[] line = new char[n];
            Arrays.fill(line, '.');
            line[qc[row]] = 'Q';
            board.add(new String(line));
        }
        res.add(board);
        return;
    }
    for (int c = 0; c < n; c++) {
        int d = r - c + n - 1, a = r + c;      // offset keeps d in [0, 2n-2]
        if (cols[c] || diag[d] || anti[a]) continue;
        cols[c] = diag[d] = anti[a] = true;
        qc[r] = c;
        place(r + 1, n, qc, cols, diag, anti, res);
        cols[c] = diag[d] = anti[a] = false;
    }
}

def total_n_queens(n):
    full = (1 << n) - 1

    def solve(cols, d1, d2):
        if cols == full:
            return 1
        count = 0
        free = full & ~(cols | d1 | d2)      # columns safe in this row
        while free:
            bit = free & -free               # lowest free column
            free ^= bit
            count += solve(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
        return count

    return solve(0, 0, 0)

The bitmask version shifts the diagonal masks one position per row, so attacked squares "slide" diagonally as you go down. It is several times faster and a great follow-up answer. Complexity is commonly quoted as O(n!) because row r has at most n − r safe columns; the actual search is much smaller thanks to diagonal pruning. For n = 8 there are 92 solutions; n = 4 has 2.

Dry run for n = 4: Row 0, col 0. Row 1: cols 0 (column), 1 (diag) blocked; try col 2. Row 2: every column is blocked, backtrack. Row 1, col 3. Row 2, col 1. Row 3: all blocked, backtrack twice to row 0. Row 0, col 1 → row 1 col 3 → row 2 col 0 → row 3 col 2: solution [".Q..", "...Q", "Q...", "..Q."]. Continuing finds the mirror solution starting at col 2.

Sudoku Solver (37): Backtracking with Constraint Tracking

Fill empty cells so every row, column and 3 × 3 box contains 1–9 exactly once. Pre-compute which digits are used in each row, column and box, then backtrack over the empty cells.

class Solution {
    int rowMask[9] = {}, colMask[9] = {}, boxMask[9] = {};
    vector<pair<int,int>> empties;

    static int box(int r, int c) { return (r / 3) * 3 + c / 3; }

    bool solve(vector<vector<char>>& b, int idx) {
        if (idx == (int)empties.size()) return true;
        auto [r, c] = empties[idx];
        int used = rowMask[r] | colMask[c] | boxMask[box(r, c)];
        for (int d = 1; d <= 9; d++) {
            int bit = 1 << d;
            if (used & bit) continue;
            rowMask[r] |= bit; colMask[c] |= bit; boxMask[box(r, c)] |= bit;
            b[r][c] = '0' + d;
            if (solve(b, idx + 1)) return true;   // stop at first solution
            rowMask[r] ^= bit; colMask[c] ^= bit; boxMask[box(r, c)] ^= bit;
            b[r][c] = '.';
        }
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') { empties.push_back({r, c}); continue; }
                int bit = 1 << (board[r][c] - '0');
                rowMask[r] |= bit; colMask[c] |= bit; boxMask[box(r, c)] |= bit;
            }
        solve(board, 0);
    }
};

Two differences from enumeration problems: the function returns bool and stops at the first full solution, and the undo only runs when the branch failed. Worst case is O(9^m) for m empty cells, but constraint checks prune almost everything on real puzzles.

The follow-up that impresses: the minimum remaining values (MRV) heuristic. Instead of filling cells in reading order, pick the empty cell with the fewest legal digits (count bits in ~used). Cells with one option get filled immediately, which is the same reasoning humans use, and it shrinks the search tree drastically on hard puzzles.

Pruning Techniques That Make Backtracking Pass

Partition to K Equal Sum Subsets (698) uses three of these at once: sort descending (big items fail fast), skip a bucket with the same current sum as a previous bucket (symmetry), and stop if an item is larger than the target. It goes from timing out to instant.

How to Analyse Backtracking Complexity

The reliable method: (number of nodes in the decision tree) × (work per node). For output problems, also count the cost of copying each answer.

For Combination Sum, N is the number of candidates, T the target and M the smallest candidate: the path is at most T/M long and each level branches at most N ways. Say that derivation out loud; interviewers care more about the reasoning than the exact formula. The general method is in time and space complexity explained.

Backtracking vs Dynamic Programming

The same problem can be either, depending on what is asked:

• "List all combinations that sum to target" → backtracking (you must output them).
• "How many combinations sum to target?" → DP (Coin Change II), because counts combine and states repeat.
• "Can the string be segmented?" → DP (Word Break). "List all segmentations" → backtracking with memo (Word Break II).
• "Minimum partitions into palindromes" → DP (Palindrome Partitioning II). "All partitions" → backtracking.

If you start with backtracking and notice the recursion's result depends only on a small state like (index, remaining), add a cache: that is top-down DP. The dynamic programming interview guide develops that transition in detail.

How Backtracking Shows Up in Interviews

Backtracking questions are common in first rounds and phone screens at Amazon, Microsoft, Google, Flipkart and many startups because they test recursion fluency in a short time. What interviewers watch:

1. Do you draw the tree? Sketching three levels of the decision tree before coding shows you understand the search space and makes duplicate handling obvious.
2. Is state restored correctly? Every add paired with a remove, every used[i] = true with a false, every board write with a restore.
3. Do you copy the path when recording? The most common silent bug.
4. Can you state complexity? "2ⁿ subsets, each copied in O(n)."
5. Follow-ups: "Return only the count" (switch to DP or bitmask counting), "inputs have duplicates" (sorted skip), "generate lazily" (iterator/generator using an explicit stack), "next permutation in place" (the O(n) algorithm, LeetCode 31).

Speak through the four template questions (path, choices, completion, validity) at the start. It reads as structured thinking, which is what the communication guide recommends for any problem.

Common Backtracking Mistakes

• Forgetting to undo one piece of state (for example, resetting used[i] but not popping the path).
• Using i + 1 vs start + 1 incorrectly. Recurse with i + 1 (the element just chosen), not start + 1, or you will produce repeated elements.
• Wrong duplicate condition: i > 0 instead of i > start.
• Not sorting before using sorted-skip or break logic.
• Returning after recording in Subsets, which stops exploration below the current node and loses most subsets.
• String concatenation in the path (path + ch) is fine in Python for clarity but costs O(L) per step; mention it if asked to optimise.

Backtracking Practice List

Word Search II combines this template with a prefix tree; it is covered in the trie interview problems guide. Once you can do all sixteen, backtracking is no longer a risk area in any interview loop.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.