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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Template | Choose, 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.
- Subsets: include or exclude each element, or loop from a start index.
- Permutations: loop over all unused elements.
- Combinations: loop from a start index to avoid reorderings.
- Duplicates: sort first, then skip an element equal to the previous one at the same level.
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 Subsets: return all subsets of a list of distinct integers.
easyFor 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.
pythondef 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 resjavaimport 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 Permutations of a list of distinct integers.
mediumAt 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.
pythondef 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 resjavaimport 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 Letter combinations of a phone number such as "23".
mediumEach 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.
pythondef 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 resjavaimport 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 Generate all well-formed strings of n pairs of parentheses.
mediumBuild 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).
pythondef 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 resjavaimport 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 Combination sum: all combinations of distinct candidates that sum to a target, reusing numbers freely.
mediumSort 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.
pythondef 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 resjavaimport 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 Subsets II: all unique subsets of a list that may contain duplicates.
mediumSort 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.
pythondef 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 resjavaimport 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 Palindrome partitioning: split a string so every piece is a palindrome.
mediumAt 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.
pythondef 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 resjavaimport 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 Word search: does a word exist in a grid by moving to adjacent cells without reusing a cell?
hardStart 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.
pythondef 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))javaimport 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 N-Queens: place n queens on an n by n board so none attack each other.
hardPlace 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.
pythondef 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 resjavaimport 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 Sudoku solver: fill the empty cells of a 9 by 9 board.
hardRecord 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.
pythondef 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)javaimport 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
- Recursion interview questions with worked solutions
- Dynamic Programming Interview Questions
- Bit manipulation interview questions with worked solutions
- String interview questions with worked solutions
- Matrix interview questions with worked solutions
- Greedy algorithm interview questions with worked solutions
More in DSA Interview Questions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions