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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.