Backtracking Pattern

What is Backtracking?

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning a path (“backtracking”) as soon as it violates constraints.

Quick Recognition: If you need to generate all possibilities, find all valid combinations, or solve constraint satisfaction problems, think Backtracking!

Pattern Recognition Checklist

Use Backtracking When

Need all combinations/permutations
Problem is about constraint satisfaction
Generate all valid solutions
Need to explore decision tree
Pruning can reduce search space

Don't Use When

Only need one solution (might use simpler approach)
Optimal solution needed (use DP instead)
Counting only (DP often better)
No way to prune invalid paths

When to Use

Combinations/Permutations

Generate all arrangements or selections

Subsets

Generate all possible subsets

Constraint Satisfaction

Sudoku, N-Queens, crosswords

Path Finding

Find all paths, word search

Core Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])  # Save a copy
        return
    
    for choice in choices:
        if is_valid(choice, path):
            # Make choice
            path.append(choice)
            
            # Explore with this choice
            backtrack(path, updated_choices)
            
            # Undo choice (backtrack)
            path.pop()

Pattern Variations

1. Subsets (All Combinations)

def subsets(nums):
    """Generate all subsets of nums"""
    result = []
    
    def backtrack(start, current):
        result.append(current[:])  # Every path is valid
        
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)  # Move forward only
            current.pop()
    
    backtrack(0, [])
    return result

# Example: [1,2,3] -> [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

2. Permutations

def permutations(nums):
    """Generate all permutations of nums"""
    result = []
    used = [False] * len(nums)
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            
            used[i] = True
            current.append(nums[i])
            
            backtrack(current)
            
            current.pop()
            used[i] = False
    
    backtrack([])
    return result

3. Combinations (Choose K)

def combinations(n, k):
    """Choose k numbers from 1 to n"""
    result = []
    
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        
        # Pruning: need k - len(current) more numbers
        remaining_needed = k - len(current)
        for i in range(start, n - remaining_needed + 2):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(1, [])
    return result

4. N-Queens

def solve_n_queens(n):
    """Place n queens on n x n board so no two attack each other"""
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check upper-left diagonal
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # Check upper-right diagonal
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return result

Classic Problems

1. Subsets

Pattern: Include or exclude each elementKey: Every path is a valid subset

2. Permutations

Pattern: Use boolean array to track used elementsKey: All positions are valid choices

3. Combination Sum

Pattern: Subsets with target sum, elements reusableKey: Start from same index (not i+1) for reuse

4. Word Search

Pattern: Grid DFS with backtrackingKey: Mark visited, restore after exploration

Common Mistakes

Avoid These Pitfalls:

Not copying path: Use path[:] or new ArrayList(path) when saving
Forgetting to backtrack: Always undo the choice after exploring
Duplicate results: Skip same values at same level for unique results
Infinite loops: Ensure progress by moving start index forward

The Backtracking Template

Every backtracking solution follows this structure:

function backtrack(path, choices):
    if is_solution(path):
        save(path)
        return
    
    for choice in choices:
        if is_valid(choice):
            make_choice(path, choice)
            backtrack(path, remaining_choices)
            undo_choice(path, choice)  # BACKTRACK!

Problem Type Quick Reference

Problem Type	Include/Exclude	Start Index	Reuse Elements
Subsets	Every node is result	i + 1	No
Combinations	Leaf nodes only	i + 1	No
Combination Sum	Leaf nodes only	i (same)	Yes
Permutations	Leaf nodes only	0 (use visited)	No
Unique Results	Skip duplicates at same level	i + 1	No

Interview Problems by Company

Medium
Hard

Problem	Company	Key Concept
Subsets	All FAANG	Basic include/exclude
Permutations	All FAANG	Used array tracking
Combination Sum	Amazon, Meta	Reusable elements
Letter Combinations	Meta	Phone keypad mapping
Word Search	Amazon, Meta	Grid backtracking

Problem	Company	Key Concept
N-Queens	Google, Meta	Constraint validation
Sudoku Solver	Amazon	Complex constraints
Palindrome Partition	Google	All valid partitions
Word Search II	Amazon	Trie + backtracking
Expression Add Operators	Meta	String manipulation

Interview Tips

How to Explain Your Approach

Script for interviews:

“This requires generating all possibilities, so I’ll use backtracking.”
“I’ll build solutions incrementally, making one choice at a time.”
“At each step, I’ll check if the current path is valid.”
“After exploring a choice, I’ll undo it (backtrack) and try the next.”
“I’ll prune invalid paths early to optimize.”

When Interviewer Says...

Interviewer Says	You Should Think
”Generate all combinations”	Backtracking
”Find all permutations”	Backtracking with used array
”All valid configurations”	Backtracking with constraints
”Can you prune?”	Early termination conditions
”Handle duplicates”	Sort + skip same at same level

Avoiding Duplicates

When input has duplicates but you need unique results:

Sort the input first
Skip duplicates at same level: if i > start and nums[i] == nums[i-1]: continue
This ensures same value isn’t used twice at same position in recursion tree

Practice Problems

Problem	Difficulty	Link
Subsets	Medium	LeetCode 78
Permutations	Medium	LeetCode 46
Combination Sum	Medium	LeetCode 39
N-Queens	Hard	LeetCode 51
Word Search	Medium	LeetCode 79

Practice Roadmap

Day 1: Subsets

Solve: Subsets, Subsets II
Focus: Include/exclude pattern

Day 2: Combinations

Solve: Combinations, Combination Sum
Focus: Target constraints

Day 3: Permutations

Solve: Permutations, Permutations II
Focus: Used array tracking

Day 4: Grid Problems

Solve: Word Search, N-Queens
Focus: 2D backtracking

Interview Tip: Draw the decision tree to visualize choices at each step. This helps identify the base case and pruning conditions.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Backtracking?

Pattern Recognition Checklist

Use Backtracking When

Don't Use When

When to Use

Combinations/Permutations

Subsets

Constraint Satisfaction

Path Finding

Core Template

Pattern Variations

1. Subsets (All Combinations)

2. Permutations

3. Combinations (Choose K)

4. N-Queens

Classic Problems

Common Mistakes

The Backtracking Template

Problem Type Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Backtracking?

​Pattern Recognition Checklist

Use Backtracking When

Don't Use When

​When to Use

Combinations/Permutations

Subsets

Constraint Satisfaction

Path Finding

​Core Template

​Pattern Variations

​1. Subsets (All Combinations)

​2. Permutations

​3. Combinations (Choose K)

​4. N-Queens

​Classic Problems

​Common Mistakes

​The Backtracking Template

​Problem Type Quick Reference

​Interview Problems by Company

​Interview Tips

​Practice Problems

​Practice Roadmap

What is Backtracking?

Pattern Recognition Checklist

When to Use

Core Template

Pattern Variations

1. Subsets (All Combinations)

2. Permutations

3. Combinations (Choose K)

4. N-Queens

Classic Problems

Common Mistakes

The Backtracking Template

Problem Type Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap