Autocoder

Backtracking interview questions with worked solutions

Last updated 2026-11-19

Backtracking builds a solution one choice at a time and undoes the last choice when it leads nowhere. It is depth-first search over the space of partial solutions: choose, explore, un-choose. Pruning, abandoning a branch as soon as it cannot lead to a valid answer, is what makes it faster than brute force.

The problems below follow the usual progression: generating all subsets and permutations, handling duplicates, building strings under a constraint, searching a grid, and finally constraint puzzles such as N-Queens and Sudoku. For the underlying idea see recursion questions. If the question asks only for a count or an optimum and sub-problems repeat, dynamic programming is usually better than enumeration.

Problems10, easy to hard
LanguagesPython and Java
TemplateChoose, explore, un-choose

The template

Define the state (the path built so far and where you are), the goal (when to record a result), the choices at each step, and the undo. In code: if goal then record a copy of the path; for each choice, if it is valid then add it, recurse, remove it.

Always append a copy of the path (path[:] or new ArrayList<>(path)) when recording a result, because the same list is mutated afterwards.

Complexity expectations

Output size dominates: 2^n subsets, n! permutations, Catalan-number many parentheses strings. State the cost as O(output size times work per result) rather than pretending it is polynomial. Pruning improves practice but not the worst case.

Backtracking interview questions with worked solutions: questions with worked answers

  1. 1

    Subsets: return all subsets of a list of distinct integers.

    easy

    For each element make two choices: skip it or take it. When every element has been decided, record a copy of the current path. This yields 2^n subsets. For [1,2,3] you get [], [3], [2], [2,3] and so on, in whichever order the choices are explored. Time O(n * 2^n), space O(n) recursion beyond the output.. Edge cases: empty input (one empty subset), single element.

    python
    def subsets(a):
        res, path = [], []
        def dfs(i):
            if i == len(a):
                res.append(path[:])
                return
            path.append(a[i])
            dfs(i + 1)
            path.pop()
            dfs(i + 1)
        dfs(0)
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<List<Integer>> subsets(int[] a) {
            List<List<Integer>> res = new ArrayList<>();
            dfs(a, 0, new ArrayList<>(), res);
            return res;
        }
        static void dfs(int[] a, int i, List<Integer> path, List<List<Integer>> res) {
            if (i == a.length) { res.add(new ArrayList<>(path)); return; }
            path.add(a[i]);
            dfs(a, i + 1, path, res);
            path.remove(path.size() - 1);
            dfs(a, i + 1, path, res);
        }
    }
  2. 2

    Permutations of a list of distinct integers.

    medium

    At each position try every element not yet used: mark it used, append, recurse, then unmark and remove. When the path has full length, record a copy. There are n! results, and the used array is the pruning that stops reuse. Time O(n * n!), space O(n) recursion beyond the output.. Edge cases: empty input (one empty permutation), a single element.

    python
    def permutations(a):
        res, path, used = [], [], [False] * len(a)
        def dfs():
            if len(path) == len(a):
                res.append(path[:])
                return
            for i in range(len(a)):
                if used[i]:
                    continue
                used[i] = True
                path.append(a[i])
                dfs()
                path.pop()
                used[i] = False
        dfs()
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<List<Integer>> permutations(int[] a) {
            List<List<Integer>> res = new ArrayList<>();
            dfs(a, new boolean[a.length], new ArrayList<>(), res);
            return res;
        }
        static void dfs(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> res) {
            if (path.size() == a.length) { res.add(new ArrayList<>(path)); return; }
            for (int i = 0; i < a.length; i++) {
                if (used[i]) continue;
                used[i] = true;
                path.add(a[i]);
                dfs(a, used, path, res);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
  3. 3

    Letter combinations of a phone number such as "23".

    medium

    Each digit maps to a few letters. Recurse over the digit positions, trying each letter for the current digit and appending it to the path. When the path has one letter per digit, record it. If the input is empty, return an empty list, not a list with an empty string. Time O(4^n * n), space O(n) recursion.. Edge cases: empty input, a digit with four letters (7 and 9), repeated digits.

    python
    def letter_combinations(digits):
        if not digits:
            return []
        m = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        res = []
        def dfs(i, cur):
            if i == len(digits):
                res.append(cur)
                return
            for ch in m[digits[i]]:
                dfs(i + 1, cur + ch)
        dfs(0, "")
        return res
    java
    import java.util.*;
    
    class Solution {
        static final String[] M = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
        static List<String> letterCombinations(String digits) {
            List<String> res = new ArrayList<>();
            if (digits.isEmpty()) return res;
            dfs(digits, 0, new StringBuilder(), res);
            return res;
        }
        static void dfs(String d, int i, StringBuilder cur, List<String> res) {
            if (i == d.length()) { res.add(cur.toString()); return; }
            for (char ch : M[d.charAt(i) - '0'].toCharArray()) {
                cur.append(ch);
                dfs(d, i + 1, cur, res);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }
  4. 4

    Generate all well-formed strings of n pairs of parentheses.

    medium

    Build the string left to right with two counters. You may add "(" while fewer than n have been used, and ")" only while the number of closers is below the number of openers. Those two rules prune every invalid prefix, so every string you complete is valid. The count is the nth Catalan number. Time O(4^n / sqrt(n)) strings, each of length 2n.. Edge cases: n = 1 (just "()"), n = 0 (one empty string).

    python
    def generate_parenthesis(n):
        res = []
        def dfs(cur, open_, close):
            if len(cur) == 2 * n:
                res.append(cur)
                return
            if open_ < n:
                dfs(cur + "(", open_ + 1, close)
            if close < open_:
                dfs(cur + ")", open_, close + 1)
        dfs("", 0, 0)
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            dfs(n, 0, 0, new StringBuilder(), res);
            return res;
        }
        static void dfs(int n, int open, int close, StringBuilder cur, List<String> res) {
            if (cur.length() == 2 * n) { res.add(cur.toString()); return; }
            if (open < n) {
                cur.append('(');
                dfs(n, open + 1, close, cur, res);
                cur.deleteCharAt(cur.length() - 1);
            }
            if (close < open) {
                cur.append(')');
                dfs(n, open, close + 1, cur, res);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }
  5. 5

    Combination sum: all combinations of distinct candidates that sum to a target, reusing numbers freely.

    medium

    Sort the candidates, then loop from a start index so that [2,3] and [3,2] are not both generated. Recurse with the same index (reuse is allowed) and a reduced remainder. When the remainder is zero, record; if a candidate exceeds the remainder, break, since later ones are larger. Time Exponential; roughly O(2^target) in the worst case. Space O(target / min candidate).. Edge cases: no combination, target equal to a candidate, a candidate larger than the target.

    python
    def combination_sum(c, target):
        c.sort()
        res, path = [], []
        def dfs(start, rem):
            if rem == 0:
                res.append(path[:])
                return
            for i in range(start, len(c)):
                if c[i] > rem:
                    break
                path.append(c[i])
                dfs(i, rem - c[i])
                path.pop()
        dfs(0, target)
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<List<Integer>> combinationSum(int[] c, int target) {
            Arrays.sort(c);
            List<List<Integer>> res = new ArrayList<>();
            dfs(c, 0, target, new ArrayList<>(), res);
            return res;
        }
        static void dfs(int[] c, int start, int rem, List<Integer> path, List<List<Integer>> res) {
            if (rem == 0) { res.add(new ArrayList<>(path)); return; }
            for (int i = start; i < c.length && c[i] <= rem; i++) {
                path.add(c[i]);
                dfs(c, i, rem - c[i], path, res);
                path.remove(path.size() - 1);
            }
        }
    }
  6. 6

    Subsets II: all unique subsets of a list that may contain duplicates.

    medium

    Sort so equal values sit together. Use the loop-from-start form: record the path at every node, then for each index i from start, skip it if it equals the previous element at the same level (i > start and a[i] == a[i-1]). That skip removes duplicate branches while still allowing a repeated value to be taken in deeper levels. Time O(n * 2^n), space O(n).. Edge cases: all elements equal, no duplicates, empty input.

    python
    def subsets_with_dup(a):
        a.sort()
        res, path = [], []
        def dfs(start):
            res.append(path[:])
            for i in range(start, len(a)):
                if i > start and a[i] == a[i - 1]:
                    continue
                path.append(a[i])
                dfs(i + 1)
                path.pop()
        dfs(0)
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<List<Integer>> subsetsWithDup(int[] a) {
            Arrays.sort(a);
            List<List<Integer>> res = new ArrayList<>();
            dfs(a, 0, new ArrayList<>(), res);
            return res;
        }
        static void dfs(int[] a, int start, List<Integer> path, List<List<Integer>> res) {
            res.add(new ArrayList<>(path));
            for (int i = start; i < a.length; i++) {
                if (i > start && a[i] == a[i - 1]) continue;
                path.add(a[i]);
                dfs(a, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }
  7. 7

    Palindrome partitioning: split a string so every piece is a palindrome.

    medium

    At each start index, try every end index; if s[start..end] is a palindrome, add it to the path and recurse from end + 1. When start reaches the end of the string, record the path. Checking palindromes by expansion is fine for short strings; precomputing a table makes each check O(1). Time O(n * 2^n), space O(n).. Edge cases: single character, a string of identical characters (many partitions), no multi-character palindromes.

    python
    def partition(s):
        res, path = [], []
        def dfs(start):
            if start == len(s):
                res.append(path[:])
                return
            for end in range(start, len(s)):
                piece = s[start:end + 1]
                if piece == piece[::-1]:
                    path.append(piece)
                    dfs(end + 1)
                    path.pop()
        dfs(0)
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<>();
            dfs(s, 0, new ArrayList<>(), res);
            return res;
        }
        static void dfs(String s, int start, List<String> path, List<List<String>> res) {
            if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
            for (int end = start; end < s.length(); end++) {
                if (isPal(s, start, end)) {
                    path.add(s.substring(start, end + 1));
                    dfs(s, end + 1, path, res);
                    path.remove(path.size() - 1);
                }
            }
        }
        static boolean isPal(String s, int l, int r) {
            while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
            return true;
        }
    }
  8. 8

    Word search: does a word exist in a grid by moving to adjacent cells without reusing a cell?

    hard

    Start a DFS from every cell that matches the first letter. At each step mark the current cell as used (overwrite it with a sentinel such as "#"), try the four neighbours for the next letter, then restore the cell on the way back. Return true as soon as the whole word is matched. Time O(rows * cols * 3^L) for word length L, space O(L).. Edge cases: word longer than the number of cells, a cell reused by mistake (forgetting to restore), repeated letters.

    python
    def exist(board, word):
        R, C = len(board), len(board[0])
        def dfs(r, c, k):
            if k == len(word):
                return True
            if r < 0 or c < 0 or r >= R or c >= C or board[r][c] != word[k]:
                return False
            tmp, board[r][c] = board[r][c], '#'
            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] = tmp
            return found
        return any(dfs(r, c, 0) for r in range(R) for c in range(C))
    java
    import java.util.*;
    
    class Solution {
        static boolean exist(char[][] b, String word) {
            for (int r = 0; r < b.length; r++)
                for (int c = 0; c < b[0].length; c++)
                    if (dfs(b, word, r, c, 0)) return true;
            return false;
        }
        static boolean dfs(char[][] b, String w, int r, int c, int k) {
            if (k == w.length()) return true;
            if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(k)) return false;
            char tmp = b[r][c];
            b[r][c] = '#';
            boolean found = dfs(b, w, r + 1, c, k + 1) || dfs(b, w, r - 1, c, k + 1)
                         || dfs(b, w, r, c + 1, k + 1) || dfs(b, w, r, c - 1, k + 1);
            b[r][c] = tmp;
            return found;
        }
    }
  9. 9

    N-Queens: place n queens on an n by n board so none attack each other.

    hard

    Place one queen per row. For each row try each column that is free of conflicts: track used columns and the two diagonals, using row - col and row + col as diagonal identifiers. Recurse to the next row; undo on return. When all rows are filled, draw the board. There are 2 solutions for n = 4. Time Roughly O(n!) with pruning, space O(n).. Edge cases: n = 1 (one solution), n = 2 and 3 (none), board drawing at the end.

    python
    def solve_n_queens(n):
        cols, d1, d2, pos, res = set(), set(), set(), [], []
        def dfs(r):
            if r == n:
                res.append(["." * c + "Q" + "." * (n - c - 1) for c in pos])
                return
            for c in range(n):
                if c in cols or (r - c) in d1 or (r + c) in d2:
                    continue
                cols.add(c); d1.add(r - c); d2.add(r + c); pos.append(c)
                dfs(r + 1)
                cols.remove(c); d1.remove(r - c); d2.remove(r + c); pos.pop()
        dfs(0)
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList<>();
            dfs(n, 0, new int[n], new boolean[n], new boolean[2 * n], new boolean[2 * n], res);
            return res;
        }
        static void dfs(int n, int r, int[] pos, boolean[] cols, boolean[] d1, boolean[] d2, List<List<String>> res) {
            if (r == n) {
                List<String> board = new ArrayList<>();
                for (int c : pos) {
                    char[] row = new char[n];
                    Arrays.fill(row, '.');
                    row[c] = 'Q';
                    board.add(new String(row));
                }
                res.add(board);
                return;
            }
            for (int c = 0; c < n; c++) {
                int a = r - c + n, b = r + c;
                if (cols[c] || d1[a] || d2[b]) continue;
                cols[c] = d1[a] = d2[b] = true;
                pos[r] = c;
                dfs(n, r + 1, pos, cols, d1, d2, res);
                cols[c] = d1[a] = d2[b] = false;
            }
        }
    }
  10. 10

    Sudoku solver: fill the empty cells of a 9 by 9 board.

    hard

    Record which digits are used in each row, column and 3 by 3 box, and list the empty cells. Fill them in order: for each empty cell try digits 1 to 9 not used in its row, column or box, place it, recurse to the next empty cell, and undo if the recursion fails. Return true when all cells are filled. Choosing the most constrained cell first speeds it up. Time Worst case exponential, fast in practice with the used-sets; space O(81).. Edge cases: a board with no solution (returns false), an already complete board, invalid starting clues.

    python
    def solve_sudoku(b):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        empties = []
        for r in range(9):
            for c in range(9):
                if b[r][c] == '.':
                    empties.append((r, c))
                else:
                    rows[r].add(b[r][c]); cols[c].add(b[r][c]); boxes[r // 3 * 3 + c // 3].add(b[r][c])
        def dfs(k):
            if k == len(empties):
                return True
            r, c = empties[k]
            bx = r // 3 * 3 + c // 3
            for d in "123456789":
                if d in rows[r] or d in cols[c] or d in boxes[bx]:
                    continue
                b[r][c] = d
                rows[r].add(d); cols[c].add(d); boxes[bx].add(d)
                if dfs(k + 1):
                    return True
                rows[r].remove(d); cols[c].remove(d); boxes[bx].remove(d)
                b[r][c] = '.'
            return False
        return dfs(0)
    java
    import java.util.*;
    
    class Solution {
        static boolean solveSudoku(char[][] b) {
            for (int r = 0; r < 9; r++)
                for (int c = 0; c < 9; c++) {
                    if (b[r][c] != '.') continue;
                    for (char d = '1'; d <= '9'; d++) {
                        if (!ok(b, r, c, d)) continue;
                        b[r][c] = d;
                        if (solveSudoku(b)) return true;
                        b[r][c] = '.';
                    }
                    return false;
                }
            return true;
        }
        static boolean ok(char[][] b, int r, int c, char d) {
            for (int i = 0; i < 9; i++) {
                if (b[r][i] == d || b[i][c] == d) return false;
                if (b[r / 3 * 3 + i / 3][c / 3 * 3 + i % 3] == d) return false;
            }
            return true;
        }
    }

Frequently asked questions

What is the difference between backtracking and brute force?

Brute force generates every candidate and then tests it. Backtracking tests as it builds and abandons a partial solution the moment it can no longer succeed, so it explores far fewer candidates.

Why do I append a copy of the path?

The path list is changed after you record it. Without a copy, every recorded result points at the same list and ends up empty or wrong.

How do I avoid duplicate results with repeated values?

Sort the input and skip a value equal to the previous one at the same recursion level. For permutations also keep the used array and skip a duplicate whose twin is unused.

When is DP better than backtracking?

When you only need a count or an optimum and the same sub-problem appears many times. If you must list every solution, backtracking is required. See dynamic programming questions.

Which problem should I learn first?

Subsets, then permutations, then N-Queens. They show include or exclude, choose from the remainder, and constraint pruning, which covers most variants.

Related guides

More in DSA Interview Questions

See all in this section