8 drills · 8 pattern exercises · 15 micro drills
Patterns used in this topic, with difficulty breakdown.
Given phone number digits, list all possible letter combinations from the keypad (like T9).
All 8 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Given phone number digits, list all possible letter combinations from the keypad (like T9).
Each digit maps to 3-4 letters. Build combinations by choosing one letter per digit and backtracking — the recursion tree has at most 4^n leaves.
Prompt
Given a string of digits 2-9, return all possible letter combinations that the number could represent (phone keypad mapping).
Solution
def letter_combinations(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, path):
if idx == len(digits):
result.append(''.join(path))
return
for c in phone[digits[idx]]:
path.append(c)
backtrack(idx + 1, path)
path.pop() # backtrack
backtrack(0, [])
return result
# Test: letter_combinations("23") == ["ad","ae","af","bd","be","bf","cd","ce","cf"]In plain English: Generate every possible ordering of a list of distinct numbers.
At each position, try every unused element. A set tracks what is used — when the path has n elements, you have a full permutation.
Prompt
Given a list of distinct integers, return all possible permutations.
Solution
def permutations(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if i in used:
continue
used.add(i)
path.append(nums[i])
backtrack(path, used)
path.pop()
used.remove(i) # backtrack
backtrack([], set())
return result
# Test: permutations([1,2,3]) has 6 permutationsIn plain English: List all ways to choose k numbers from 1 to n (order does not matter).
To avoid duplicates, always pick elements in increasing order — start each recursive call from the next number after the last picked.
Prompt
Given n and k, return all combinations of k numbers from 1 to n.
Solution
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
# prune: not enough numbers left
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
# Test: combine(4, 2) == [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]In plain English: Find all ways to pick numbers from a list (reuse allowed) that add up to a target sum.
Like combinations, but allow reuse by not advancing the start index. Prune when the remaining target goes negative.
Prompt
Given an array of distinct integers (candidates) and a target, find all unique combinations that sum to the target. Each number may be reused unlimited times.
Solution
def combination_sum(candidates, target):
result = []
candidates.sort()
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # prune: sorted, so all subsequent are too large
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, not i+1: reuse allowed
path.pop()
backtrack(0, [], target)
return result
# Test: combination_sum([2,3,6,7], 7) == [[2,2,3],[7]]In plain English: Place 4 queens on a 4x4 chessboard so none can attack another (no shared row, column, or diagonal).
Place one queen per row. Track occupied columns and diagonals with sets — prune immediately when a column or diagonal conflicts.
Prompt
Place 4 queens on a 4x4 board so that no two queens threaten each other. Return all solutions.
Solution
def solve_n_queens(n=4):
result = []
def backtrack(row, cols, diag1, diag2, board):
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 diag1 or (row + col) in diag2:
continue # prune: conflict
board[row][col] = 'Q'
backtrack(row + 1, cols | {col}, diag1 | {row - col},
diag2 | {row + col}, board)
board[row][col] = '.'
backtrack(0, set(), set(), set(), [['.']*n for _ in range(n)])
return result
# Test: len(solve_n_queens(4)) == 2In plain English: Check if you can spell a word by tracing a path through adjacent cells in a grid (each cell used once).
DFS from each cell matching the first letter. Mark cells as visited during the search and unmark on backtrack — prune when characters do not match.
Prompt
Given a 2D board of characters and a word, determine if the word exists in the grid. You can move up, down, left, right and cannot reuse a cell.
Solution
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
return False
tmp, board[i][j] = board[i][j], '#' # mark visited
found = any(dfs(i+di, j+dj, k+1) for di, dj in [(-1,0),(1,0),(0,-1),(0,1)])
board[i][j] = tmp # backtrack
return found
return any(dfs(i, j, 0) for i in range(m) for j in range(n))
# Test: exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED") == TrueIn plain English: Split a string into pieces where every piece reads the same forwards and backwards.
Try every prefix as a palindrome candidate. If valid, recurse on the remaining suffix. Backtrack when no valid palindrome prefix exists.
Prompt
Given a string s, partition it such that every substring is a palindrome. Return all possible partitions.
Solution
def palindrome_partition(s):
result = []
def is_pal(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
sub = s[start:end]
# prune: only recurse when prefix is a palindrome, skipping invalid branches early
if is_pal(sub):
path.append(sub)
backtrack(end, path)
path.pop() # undo choice so sibling branches start clean
backtrack(0, [])
return result
# Test: palindrome_partition("aab") == [["a","a","b"],["aa","b"]]In plain English: Generate every possible way to arrange n pairs of parentheses so they're all properly matched.
Backtrack with two counters: open and close. You can add '(' if open < n, and ')' if close < open. The close < open constraint ensures validity. Base case: length == 2*n.
Prompt
Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses.
Solution
def generate_parenthesis(n):
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append(''.join(path))
return
# can add '(' as long as we haven't used all n opens
if open_count < n:
path.append('(')
backtrack(path, open_count + 1, close_count)
path.pop()
# can add ')' only when unmatched opens exist, ensuring validity
if close_count < open_count:
path.append(')')
backtrack(path, open_count, close_count + 1)
path.pop()
backtrack([], 0, 0)
return result
# Test: generate_parenthesis(3)
# == ["((()))","(()())","(())()","()(())","()()()"]
# Test: generate_parenthesis(1) == ["()"]8 exercises: spot the signals, pick the method, avoid the trap.
Given digits 2-9, return all possible letter combinations (phone keypad).
Signals
For each digit, try each letter. Recurse on remaining digits. Collect at end. O(4^n).
Trap
This is a Cartesian product, not permutations. The order of digits is fixed.
Return all permutations of a list of distinct integers.
Signals
At each position, choose from unused elements. Track used set. Collect when path length = n. O(n! * n).
Trap
Don't confuse with combinations. Permutations care about order: [1,2] ≠ [2,1].
Given n and k, return all combinations of k numbers from 1 to n.
Signals
From index start, choose next number, recurse with start+1. Collect when path has k elements. O(C(n,k)).
Trap
The key to avoiding duplicates: always pick in ascending order (start from last_picked + 1).
Find all unique combinations that sum to target. Numbers can be reused.
Signals
Recurse: for each candidate from start, subtract from target, recurse (allowing reuse). Prune when target < 0.
Trap
To allow reuse, recurse with same index (not start+1). To avoid duplicates, sort and skip.
Place 4 queens on 4x4 board with no two threatening each other.
Signals
Row by row, try each column. Use sets for occupied columns and diagonals. Prune invalid placements.
Trap
Diagonals: row-col identifies one diagonal, row+col the other. Use sets to track both.
Does a word exist in a 2D grid? Move up/down/left/right, no cell reuse.
Signals
For each cell matching word[0], DFS in 4 directions. Mark visited, unmark on backtrack. O(m*n*4^L).
Trap
Must unmark visited cells on backtrack (not just mark) — other paths might need them.
Partition a string so every substring is a palindrome. Return all partitions.
Signals
At each position, try all prefixes that are palindromes. Recurse on remaining suffix. Collect at end.
Precompute is_palindrome[i][j] table to speed up palindrome checks within the backtracking.
Trap
The palindrome check inside backtracking can be precomputed with DP to avoid redundant work.
Generate all combinations of n pairs of well-formed parentheses.
Signals
Track open and close counts. Add '(' if open < n. Add ')' if close < open. O(4^n / sqrt(n)).
Build from smaller n using dp[n] = '(' + dp[i] + ')' + dp[n-1-i]. Same complexity.
Trap
The constraint is close ≤ open ≤ n. Don't just generate all 2^(2n) strings and filter.
15 quick recall drills to reinforce this topic.
Each digit maps to letters. At each position, branch on all mapped letters. O(4^n) worst case.
def letterCombinations(digits):
if not digits: return []
phone = {'2':'abc','3':'def','4':'ghi','5':'jkl',
'6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
res = []
def backtrack(i, path):
if i == len(digits):
res.append(''.join(path))
return
for ch in phone[digits[i]]:
path.append(ch)
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resStack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.
stack = []
stack.append(x)
stack.pop()Monotonic stacks find next-greater/smaller elements in O(n). Key for histogram and temperature problems.
stack = []
for x in a:
while stack and stack[-1] >= x:
stack.pop()
stack.append(x)Permutations use a used[] mask instead of start-index. Each level tries all unused elements. O(n!) results.
def permute(nums):
res = []
def bt(path, used):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if not used[i]:
used[i] = True
path.append(nums[i])
bt(path, used)
path.pop()
used[i] = False
bt([], [False]*len(nums))
return resMove-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wNext-greater-element uses a decreasing stack. Shows up in stock span and temperature problems.
result = [-1] * len(a)
stack = []
for i in range(len(a) - 1, -1, -1):
while stack and stack[-1] <= a[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(a[i])Reuse allowed: recurse with start=i (not i+1). Sort + break when candidate > remaining for pruning.
def combinationSum(candidates, target):
res = []
def backtrack(start, path, remaining):
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, not i+1
path.pop()
candidates.sort()
backtrack(0, [], target)
return resNo reuse: recurse with i+1. Skip duplicates: if i > start and same as previous, skip. Must sort first.
def combinationSum2(candidates, target):
res = []
candidates.sort()
def backtrack(start, path, remaining):
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
if i > start and candidates[i] == candidates[i-1]: continue
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return resSort + fix first + two-pointer on remainder. Skip duplicates at all three levels.
a.sort()
for i in range(len(a)-2):
if i and a[i] == a[i-1]: continue
l, r = i+1, len(a)-1
while l < r:
s = a[i] + a[l] + a[r]
if s < 0: l += 1
elif s > 0: r -= 1
else:
res.append([a[i], a[l], a[r]])
l += 1
while l < r and a[l] == a[l-1]: l += 1Place queens row by row, checking column and diagonal conflicts. Classic backtracking with implicit undo.
def solveNQueens(n):
res = []
board = [-1] * n
def backtrack(row):
if row == n:
res.append(['.'*c + 'Q' + '.'*(n-c-1) for c in board])
return
for col in range(n):
if all(board[i] != col and abs(board[i]-col) != row-i
for i in range(row)):
board[row] = col
backtrack(row + 1)
board[row] = -1
backtrack(0)
return resGrid backtracking: mark cell as visited, explore 4 directions, unmark on backtrack. O(m*n*4^L).
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word): return True
if i < 0 or i >= m or j < 0 or j >= n: return False
if board[i][j] != word[k]: return False
tmp, board[i][j] = board[i][j], '#' # mark visited
for di, dj in (0,1),(0,-1),(1,0),(-1,0):
if dfs(i+di, j+dj, k+1): return True
board[i][j] = tmp # unmark
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0): return True
return FalseTry every prefix as a partition. If it's a palindrome, recurse on the rest. Enumerate all valid partitions.
def partition(s):
res = []
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start + 1, len(s) + 1):
sub = s[start:end]
if sub == sub[::-1]:
path.append(sub)
backtrack(end, path)
path.pop()
backtrack(0, [])
return resTrack open/close counts. Only add close paren when close < open.
def bt(o, c, cur):
if len(cur) == 2*n: res.append(cur); return
if o < n: bt(o+1, c, cur+'(')
if c < o: bt(o, c+1, cur+')')Sortedness check is a precondition guard for binary search and merge operations.
all(a[i] <= a[i+1] for i in range(len(a)-1))