NeetCode 150 · Backtracking

Backtracking Problems

Backtracking explores all possibilities by making a choice, recursing, then undoing that choice. The key is knowing when to prune early.

Problems: 9
Easy: 0
Medium: 8
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Medium ArrayBacktrackingBit Manipulation
Given integer array nums with unique elements, return all possible subsets (the power set).
Test Cases
subsets([1,2,3]) → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] subsets([0]) → [[],[0]]
backtrack with start indexsnapshot currentO(n·2^n)
At each step, decide to include or exclude each element. A backtracking function with a start index naturally generates all subsets.
Python Solution
def subsets(nums): result = [] def backtrack(start, current): result.append(current[:]) # snapshot — every state is a subset for i in range(start, len(nums)): current.append(nums[i]) backtrack(i + 1, current) current.pop() backtrack(0, []) return result
Key idea: Every intermediate state of the backtracking is a valid subset. Snapshot it on entry, then try adding each remaining element. Remove it (backtrack) after the recursive call.
Time: O(n·2^n).
Space: O(n) recursion depth.
02 Medium ArrayBacktracking
Given array of distinct integers candidates and target integer, return all unique combinations that sum to target. The same number may be used unlimited times.
Test Cases
combinationSum([2,3,6,7], 7) → [[2,2,3],[7]] combinationSum([2,3,5], 8) → [[2,2,2,2],[2,3,3],[3,5]]
backtrack with reuse (same i)pruning > remainingO(n^(t/m))
Recurse with the same start index i (allowing reuse). Prune branches where the candidate exceeds the remaining target.
Python Solution
def combinationSum(candidates, target): result = [] def backtrack(start, current, remaining): if remaining == 0: result.append(current[:]) return for i in range(start, len(candidates)): if candidates[i] <= remaining: current.append(candidates[i]) backtrack(i, current, remaining - candidates[i]) # i, not i+1 (reuse) current.pop() backtrack(0, [], target) return result
Key idea: Pass the same index i (not i+1) to allow reuse of the same element. Prune when candidates[i] > remaining.
Time: O(n^(T/M)) — T=target, M=min candidate.
Space: O(T/M) recursion depth.
03 Medium ArrayBacktracking
Given array nums of distinct integers, return all possible permutations.
Test Cases
permute([1,2,3]) → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] permute([0,1]) → [[0,1],[1,0]]
swap backtrackO(n! · n)in-place
At each position, try swapping each remaining element into that position. Recurse for the next position, then swap back.
Python Solution
def permute(nums): result = [] def backtrack(start): if start == len(nums): result.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] = nums[i], nums[start] # swap backtrack(start + 1) nums[start], nums[i] = nums[i], nums[start] # swap back backtrack(0) return result
Key idea: Fix each element at position start by swapping it there, recurse to fill the rest, then swap back. This generates all n! permutations in-place.
Time: O(n! · n).
Space: O(n) recursion depth.
04 Medium ArrayBacktrackingBit Manipulation
Given integer array nums that may contain duplicates, return all possible subsets. The solution must not contain duplicate subsets.
Test Cases
subsetsWithDup([1,2,2]) → [[],[1],[1,2],[1,2,2],[2],[2,2]] subsetsWithDup([0]) → [[],[0]]
sort firstskip duplicate siblingsO(n·2^n)
Sort the array. Skip an element at position i if it equals the previous element AND i > start (to avoid duplicate subsets at the same level).
Python Solution
def subsetsWithDup(nums): nums.sort() result = [] def backtrack(start, current): result.append(current[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # skip duplicate at same level current.append(nums[i]) backtrack(i + 1, current) current.pop() backtrack(0, []) return result
Key idea: Sort first so duplicates are adjacent. At each backtracking level, skip elements that are the same as the previous sibling (i > start and nums[i] == nums[i-1]) to avoid duplicate subsets.
Time: O(n·2^n).
Space: O(n).
05 Medium ArrayBacktracking
Given candidates and target, find all unique combinations summing to target. Each number may only be used once, and candidates may contain duplicates.
Test Cases
combinationSum2([10,1,2,7,6,1,5], 8) → [[1,1,6],[1,2,5],[1,7],[2,6]] combinationSum2([2,5,2,1,2], 5) → [[1,2,2],[5]]
sort+skip dupsi > start skipuse i+1 (no reuse)
Sort first. Skip an element if it's a duplicate of the previous element at the same level (i > start and candidates[i] == candidates[i-1]).
Python Solution
def combinationSum2(candidates, target): candidates.sort() result = [] def backtrack(start, current, remaining): if remaining == 0: result.append(current[:]) return for i in range(start, len(candidates)): if candidates[i] > remaining: break # sorted, so all remaining are too large if i > start and candidates[i] == candidates[i - 1]: continue # skip duplicate at same level current.append(candidates[i]) backtrack(i + 1, current, remaining - candidates[i]) current.pop() backtrack(0, [], target) return result
Key idea: Sort + skip duplicates at the same level. Use i+1 (not i) to prevent reusing the same element. The sort also enables early termination when candidates exceed remaining.
Time: O(2^n).
Space: O(n).
06 Medium ArrayBacktrackingMatrix
Given m×n grid and string word, return True if the word can be constructed by sequentially adjacent cells (horizontal or vertical). Each cell may only be used once.
Test Cases
exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED') → True exist(same_board, 'SEE') → True exist(same_board, 'ABCB') → False
DFS backtrackin-place mark visited4-directional
DFS from each cell. Mark a cell as visited to prevent reuse. Restore it after backtracking.
Python Solution
def exist(board, word): rows, cols = len(board), len(board[0]) def dfs(r, c, idx): if idx == len(word): return True if (r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]): return False temp = board[r][c] board[r][c] = '#' # mark visited found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1) or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1)) board[r][c] = temp # restore return found for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True return False
Key idea: Try DFS from every cell. Mark cells as '#' to prevent revisiting. After DFS, restore the original value (backtrack). Return True as soon as the full word is found.
Time: O(m·n·4·3^(L-1)) where L=word length.
Space: O(L) recursion depth.
07 Medium StringBacktrackingDP
Given string s, partition it such that every substring is a palindrome. Return all possible partitions.
Test Cases
partition('aab') → [['a','a','b'],['aa','b']] partition('a') → [['a']]
backtrack substringsisPalindrome checkO(n·2^n)
Backtrack over all possible first substrings. If the first part is a palindrome, recurse on the rest.
Python Solution
def partition(s): result = [] def backtrack(start, current): if start == len(s): result.append(current[:]) return for end in range(start + 1, len(s) + 1): substr = s[start:end] if substr == substr[::-1]: # palindrome check current.append(substr) backtrack(end, current) current.pop() backtrack(0, []) return result
Key idea: For each starting position, try all substrings of increasing length. If the substring is a palindrome, add it to the current partition and recurse. Backtrack by popping.
Time: O(n·2^n).
Space: O(n).
08 Medium StringBacktrackingHash Map
Given digits 2-9, return all possible letter combinations that the number could represent (like a phone keypad).
Test Cases
letterCombinations('23') → ['ad','ae','af','bd','be','bf','cd','ce','cf'] letterCombinations('') → []
phone map dictbacktrack by digitO(4^n · n)
Map each digit to its letters. Backtrack: for each digit, try each letter and recurse to the next digit.
Python Solution
def letterCombinations(digits): if not digits: return [] phone = {'2':'abc','3':'def','4':'ghi','5':'jkl', '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'} result = [] def backtrack(idx, current): if idx == len(digits): result.append(''.join(current)) return for ch in phone[digits[idx]]: current.append(ch) backtrack(idx + 1, current) current.pop() backtrack(0, []) return result
Key idea: Build combinations character by character. For each digit position, try each mapped letter and recurse. When all digits are processed, add the combination to results.
Time: O(4^n · n) — 4 letters max per digit.
Space: O(n).
09 Hard ArrayBacktracking
Place n queens on an n×n chessboard so no two queens attack each other. Return all distinct solutions.
Test Cases
solveNQueens(4) → ['.Q..','...Q','Q...','..Q.'] and ['..Q.','Q...','...Q','.Q..'] solveNQueens(1) → [['Q']]
col/pos_diag/neg_diag setsrow-by-row placementO(n!)
Place one queen per row. Track which columns, positive diagonals (r+c), and negative diagonals (r-c) are occupied to prune invalid placements.
Python Solution
def solveNQueens(n): result = [] cols, pos_diag, neg_diag = set(), set(), set() board = [['.'] * n for _ in range(n)] def backtrack(row): if row == n: result.append([''.join(r) for r in board]) return for col in range(n): if col in cols or (row+col) in pos_diag or (row-col) in neg_diag: continue cols.add(col); pos_diag.add(row+col); neg_diag.add(row-col) board[row][col] = 'Q' backtrack(row + 1) cols.remove(col); pos_diag.remove(row+col); neg_diag.remove(row-col) board[row][col] = '.' backtrack(0) return result
Key idea: Place queens row by row. Three sets track attacked columns and diagonals. A cell is safe only if it's not in any set. Add/remove from sets as you recurse/backtrack.
Time: O(n!).
Space: O(n²).
← Prev Category Next Category →