Backtracking Algorithm Explained: Master Recursion for Coding Interviews
Complete guide to backtracking with choose-explore-unchoose pattern. Solve N-Queens, Sudoku, permutations, and combinations. Learn constraint pruning techniques with Python examples for technical interviews
The Moment Backtracking Finally Made Sense
I'll be honestâbacktracking was one of those algorithmic concepts that felt like magic when I first encountered it. My interviewer asked me to generate all permutations of a string, and while I knew it involved recursion, I had no idea how to systematically explore and "undo" choices to avoid duplicates and find all solutions.
Then someone explained the three-word mantra that changed everything: "Choose, Explore, Unchoose." Suddenly, backtracking wasn't mysterious anymore. It was just a systematic way to explore all possibilities by trying each option, recursing deeper, and then undoing that choice to try the next option.
In this guide, I'll demystify backtracking the same way it was demystified for me. No confusing abstractionsâjust clear patterns, practical examples, and the mental models you need to solve any backtracking problem confidently.
What Is Backtracking, Really?
Backtracking is a systematic way to explore all possible solutions to a problem by making choices, exploring their consequences, and "backing up" (undoing choices) when they lead to dead ends.
Think of it like exploring a maze:
- You try a path (make a choice)
- You walk down that path (explore)
- If you hit a dead end, you walk back to the last intersection (backtrack/unchoose)
- You try the next unexplored path
- Repeat until you've tried all paths
The universal backtracking template:
def backtrack(state, choices):
"""
Universal backtracking template.
State: current partial solution
Choices: available options at this point
"""
# Base case: found complete solution
if is_solution(state):
output(state)
return
# Try each available choice
for choice in choices:
# 1. Choose: add choice to state
make_choice(state, choice)
# 2. Explore: recurse with updated state
backtrack(state, get_new_choices(state))
# 3. Unchoose: remove choice from state (backtrack)
undo_choice(state, choice)
That's it. Every backtracking problem follows this pattern. The only things that change are:
- What constitutes a "solution"
- What "choices" are available
- How you "make" and "undo" choices
When to Recognize a Backtracking Problem
Your brain should immediately think "backtracking" when you see:
Clear indicators:
- "Generate ALL possible..." (permutations, combinations, subsets)
- "Find ALL solutions..." (N-Queens, Sudoku)
- "Count the number of ways to..." (when you need to explore all paths)
- Making a series of choices where future choices depend on past ones
- Problems with constraints that can rule out partial solutions early
Keywords that scream backtracking:
- Permutations, combinations, subsets
- N-Queens, Sudoku solver
- Word search in grid
- Path finding with constraints
- Partition problems
- Generate parentheses
If you can solve it by trying every possibility and some possibilities can be eliminated early (before exploring fully), it's probably backtracking.
The Choose-Explore-Unchoose Pattern
Let me break down the three steps with a concrete example: generating all subsets of [1, 2, 3].
Step 1: Choose
Make a decision. Add an element to your current subset.
current_subset.append(nums[i]) # Choose to include nums[i]
Step 2: Explore
Recursively explore what happens after making that choice.
backtrack(i + 1, current_subset) # Explore with this choice
Step 3: Unchoose
Undo your choice so you can try the next option.
current_subset.pop() # Unchoose - remove nums[i] to try next
Complete example:
def generate_subsets(nums):
"""
Generate all subsets using backtracking.
Classic choose-explore-unchoose pattern.
"""
result = []
def backtrack(start, current):
# Base case: we've made a choice for all positions
# Add current subset to results
result.append(current[:]) # Copy current state
# Try adding each remaining element
for i in range(start, len(nums)):
# Choose: include nums[i]
current.append(nums[i])
# Explore: recurse with nums[i] included
backtrack(i + 1, current)
# Unchoose: remove nums[i] to try next option
current.pop()
backtrack(0, [])
return result
Test: generate_subsets([1, 2, 3])Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
The recursion tree visualization:
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
|
[1,2,3]
At each level, we choose to include an element, explore all possibilities with that choice, then unchoose and try the next element.
Pattern 1: Generating Combinations and Permutations
These are the "bread and butter" of backtracking. Master these, and you'll recognize the pattern everywhere.
Permutations: Order Matters
Problem: Generate all arrangements of elements where order matters.
def permutations(nums):
"""
Generate all permutations where order matters.
Uses used[] array to track which elements are in current permutation.
"""
result = []
used = [False] * len(nums)
def backtrack(current):
# Base case: built complete permutation
if len(current) == len(nums):
result.append(current[:])
return
# Try each unused number
for i in range(len(nums)):
if used[i]:
continue # Skip if already in current permutation
# Choose: mark as used, add to current
used[i] = True
current.append(nums[i])
# Explore: continue building permutation
backtrack(current)
# Unchoose: mark as unused, remove from current
current.pop()
used[i] = False
backtrack([])
return result
Test: permutations([1, 2, 3])Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Key insight: We need a used array because for permutations, each element can appear anywhere, so we need to track what's already in our current permutation.
Time complexity: O(n! Ă n) - n! permutations, O(n) to copy each Space complexity: O(n) for recursion depth and current permutation
Combinations: Order Doesn't Matter
Problem: Generate all selections of k elements where order doesn't matter.
def combinations(n, k):
"""
Generate all combinations of k numbers from 1 to n.
Use start index to avoid duplicates.
"""
result = []
def backtrack(start, current):
# Base case: selected k elements
if len(current) == k:
result.append(current[:])
return
# Try each number from start to n
for i in range(start, n + 1):
# Choose: add number i
current.append(i)
# Explore: continue from i+1 (avoid duplicates)
backtrack(i + 1, current)
# Unchoose: remove number i
current.pop()
backtrack(1, [])
return result
Test: combinations(4, 2)Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
Key insight: We use a start index and only explore elements after the current one. This naturally avoids duplicates since 1,2 and 2,1 are the same combination.
Pattern 2: Constraint Satisfaction Problems
These problems have explicit constraints that let you prune the search space earlyâthe hallmark of efficient backtracking.
N-Queens Problem
Problem: Place N queens on an NĂN chessboard so no two queens attack each other.
This is THE classic backtracking problem. It demonstrates constraint checking and pruning beautifully.
def solve_n_queens(n):
"""
Solve N-Queens using backtracking with constraint checking.
Place queens row by row, checking column and diagonal conflicts.
"""
result = []
board = [['.'] * n for _ in range(n)]
# Track occupied columns and diagonals
cols = set()
diag1 = set() # row - col is constant for each diagonal /
diag2 = set() # row + col is constant for each diagonal \
def backtrack(row):
# Base case: placed queens in all rows
if row == n:
result.append([''.join(row) for row in board])
return
# Try placing queen in each column of this row
for col in range(n):
# Check constraints: is this position safe?
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # Conflict detected, skip this position
# Choose: place queen
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# Explore: move to next row
backtrack(row + 1)
# Unchoose: remove queen
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
Test: solve_n_queens(4)Output: Two solutions for 4-Queens
Key insight: We place queens row by row (each row must have exactly one queen). For each row, we try each column, but skip positions that would create conflicts. The sets track which columns and diagonals are occupied, allowing O(1) conflict checking.
The power of pruning: Without constraint checking, we'd explore all n^n possible placements. With constraints, we prune entire branches early, making it feasible even for larger n.
Sudoku Solver
Problem: Fill a 9Ă9 grid so each row, column, and 3Ă3 box contains digits 1-9.
def solve_sudoku(board):
"""
Solve Sudoku using backtracking.
Fill empty cells while checking row/column/box constraints.
"""
def is_valid(board, row, col, num):
"""Check if placing num at (row, col) is valid."""
# Check row
if str(num) in board[row]:
return False
# Check column
if str(num) in [board[i][col] for i in range(9)]:
return False
# Check 3x3 box
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for i in range(box_row, box_row + 3):
for j in range(box_col, box_col + 3):
if board[i][j] == str(num):
return False
return True
def backtrack():
# Find next empty cell
for row in range(9):
for col in range(9):
if board[row][col] == '.':
# Try each digit
for num in range(1, 10):
if is_valid(board, row, col, num):
# Choose: place digit
board[row][col] = str(num)
# Explore: continue solving
if backtrack():
return True
# Unchoose: backtrack
board[row][col] = '.'
return False # No valid digit for this cell
return True # All cells filled successfully
backtrack()
return board
Key insight: We fill cells one by one, trying each digit 1-9. If a digit doesn't violate constraints, we place it and recurse. If we later find no solution with that choice, we backtrack and try the next digit.
Pattern 3: Grid and Path Exploration
When you need to explore all paths in a grid with certain properties.
Word Search in Grid
Problem: Given a 2D board and a word, find if the word exists in the grid (can move up/down/left/right, can't reuse cells).
def word_search(board, word):
"""
Search for word in grid using backtracking.
Explore all 4 directions, mark visited cells.
"""
rows, cols = len(board), len(board[0])
def backtrack(row, col, index):
# Base case: found entire word
if index == len(word):
return True
# Check boundaries and if current cell matches
if (row < 0 or row >= rows or col < 0 or col >= cols or
board[row][col] != word[index]):
return False
# Choose: mark cell as visited
temp = board[row][col]
board[row][col] = '#' # Mark as visited
# Explore: try all 4 directions
found = (backtrack(row + 1, col, index + 1) or
backtrack(row - 1, col, index + 1) or
backtrack(row, col + 1, index + 1) or
backtrack(row, col - 1, index + 1))
# Unchoose: restore cell
board[row][col] = temp
return found
# Try starting from each cell
for i in range(rows):
for j in range(cols):
if backtrack(i, j, 0):
return True
return False
Test:
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word_search(board, "ABCCED") # True
word_search(board, "SEE") # True
word_search(board, "ABCB") # False
Key insight: We mark cells as visited by temporarily changing their value, then restore after exploring. This prevents us from using the same cell twice in a path.
Pattern 4: Partition and Split Problems
Problems where you need to try all ways to partition or split something.
Palindrome Partitioning
Problem: Partition a string so every substring is a palindrome. Return all possible partitionings.
def palindrome_partition(s):
"""
Partition string into palindromes using backtracking.
Try all split points, check if substring is palindrome.
"""
result = []
def is_palindrome(sub):
"""Check if substring is palindrome."""
return sub == sub[::-1]
def backtrack(start, current):
# Base case: partitioned entire string
if start == len(s):
result.append(current[:])
return
# Try all possible end points from current start
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
# Only continue if current substring is palindrome
if is_palindrome(substring):
# Choose: add this palindrome substring
current.append(substring)
# Explore: partition rest of string
backtrack(end, current)
# Unchoose: remove substring to try next split
current.pop()
backtrack(0, [])
return result
Test: palindrome_partition("aab")Output: [["a","a","b"], ["aa","b"]]
Key insight: At each position, we try all possible substrings starting from that position. We only recurse if the substring is a palindromeâthis is constraint pruning!
Common Backtracking Optimizations
Optimization 1: Early Pruning
Check constraints BEFORE recursing, not after. This avoids exploring entire branches that will fail.
# Bad: explore then check
backtrack(new_state)
if not is_valid(new_state):
return
# Good: check then explore
if not is_valid(new_state):
return
backtrack(new_state)
Optimization 2: Sort Input
For some problems, sorting allows you to break early when values get too large.
# For combination sum: if nums is sorted and current num > target
if nums[i] > target:
break # All remaining numbers are also too large
Optimization 3: Skip Duplicates
When input has duplicates and you want unique solutions:
# Skip duplicate elements at same recursion level
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # Skip duplicate
backtrack(i + 1, current)
The Backtracking Decision Tree
When you encounter a backtracking problem, ask yourself:
1. What is a complete solution?
- Define your base case clearly
- When do you add to results?
2. What choices do I have at each step?
- What can I add to current state?
- What are the options to explore?
3. What constraints must be satisfied?
- When should I prune (not explore further)?
- What makes a choice invalid?
4. How do I represent state?
- List, set, grid markers?
- What do I need to track?
5. How do I make/unmake choices?
- Append/pop from list?
- Mark/unmark cells?
- Add/remove from set?
Time Complexity: Why Backtracking Can Be Slow
Backtracking explores exponential search spaces:
- Subsets: O(2^n) - each element is in or out
- Permutations: O(n!) - n choices for first, n-1 for second...
- N-Queens: O(n!) with pruning
- Sudoku: O(9^m) where m is number of empty cells
This is why backtracking is often only feasible for small inputs (n ⤠20 typically). But with good pruning, it becomes practical for many problems.
My Practice Strategy
Here's how I went from confused to confident with backtracking:
Week 1: Master the Template
- Implement subsets, permutations, combinations 5 times each
- Focus on the choose-explore-unchoose rhythm
- Draw recursion trees on paper
Week 2: Add Constraints
- Solve N-Queens for n=4, 5, 6, 8
- Implement Sudoku solver
- Focus on pruning techniques
Week 3: Grid Problems
- Word search and variations
- Path finding problems
- Practice modifying state (marking visited)
Week 4: Mixed Practice
- 20-30 backtracking problems of varying difficulty
- Practice recognizing the pattern from problem description
- Time yourself: recognition in 1 minute, solution in 20 minutes
Real Interview Experience
I was asked: "Generate all valid combinations of n pairs of parentheses."
My approach:
- Recognized backtracking: "generate all" + "valid" (constraint)
- State: current string, count of open/close parentheses used
- Choices: add '(' or add ')'
- Constraints: can't add ')' if it would exceed '(', can't exceed n opens
I coded it in 12 minutes:
def generate_parentheses(n):
result = []
def backtrack(current, open_count, close_count):
# Base case: used all n pairs
if len(current) == 2 * n:
result.append(current)
return
# Can add '(' if haven't used all n
if open_count < n:
backtrack(current + '(', open_count + 1, close_count)
# Can add ')' if it wouldn't exceed '('
if close_count < open_count:
backtrack(current + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
The interviewer was impressed by how I verbalized the pattern recognition and constraint checking.
Conclusion: Your Backtracking Mastery Roadmap
Backtracking isn't magicâit's systematic exploration with the discipline to undo choices and try alternatives. Here's what matters:
- The mantra: Choose, Explore, Unchoose
- Recognize the pattern: "all possible," "generate," "find all"
- Prune early: Check constraints before recursing
- Practice the template: Until it's muscle memory
Start with simple problems like subsets and permutations. Once the pattern clicks, move to constraint problems like N-Queens. Finally, tackle grid and partition problems.
Within 3-4 weeks of focused practice, you'll recognize backtracking problems instantly and code solutions confidently.
Remember: every expert was once a beginner drawing recursion trees on paper. The difference is they kept practicing until the choose-explore-unchoose rhythm became second nature.
Happy coding, and may your backtracking always terminate!
If you found this guide helpful, share it with others learning algorithms. Backtracking is one of those topics that seems hard until the pattern clicksâthen it becomes a powerful problem-solving tool. If this guide helped you master backtracking or understand the generate-all-solutions pattern, I'd love to hear about it! Connect with me on Twitter or LinkedIn.
Support My Work
If this guide helped you finally understand backtracking, gave you confidence to solve "generate all" problems, or helped you ace a coding interview, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.
â Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!
Cover image by Filip Mroz on Unsplash