BeginnerAdvanced Patterns

Backtracking

Explore decision trees with pruning for subsets, permutations, and constraint satisfaction

Time: O(b^d)
Space: O(d)
Pattern Overview

Core Idea

Build partial solutions, recurse, and undo choices; prune invalid or dominated branches early.

When to Use

Use when search space is exponential but constraints prune heavily.

General Recognition Cues
General indicators that this pattern might be applicable
  • Subsets/permutations
  • N-Queens
  • Sudoku
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Subsets

Choose/skip each element

When to Use This Variant
  • Power set
Use Case
All combinations
Advantages
  • Simple template
Implementation
def subsets(nums):
    res=[]
    def dfs(i, path):
        if i==len(nums): res.append(path[:]); return
        dfs(i+1, path)
        path.append(nums[i]); dfs(i+1, path); path.pop()
    dfs(0, [])
    return res
2

Permutations

Swap/visited to permute

When to Use This Variant
  • All orders
Use Case
Orderings
Advantages
  • Pruning duplicates
Implementation
def permutations(nums):
    res=[]; used=[False]*len(nums)
    def dfs(path):
        if len(path)==len(nums): res.append(path[:]); return
        for i,x in enumerate(nums):
            if used[i]: continue
            used[i]=True; path.append(x); dfs(path); path.pop(); used[i]=False
    dfs([]); return res
3

N-Queens/Sudoku

Place with constraints

When to Use This Variant
  • Row/col/diag rules
Use Case
CSP
Advantages
  • Constraint pruning
Implementation
def solve_n_queens(n):
    cols=set(); d1=set(); d2=set(); res=[]; board=[['.']*n for _ in range(n)]
    def dfs(r):
        if r==n: res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or (r-c) in d1 or (r+c) in d2: continue
            cols.add(c); d1.add(r-c); d2.add(r+c); board[r][c]='Q'
            dfs(r+1)
            board[r][c]='.'; cols.remove(c); d1.remove(r-c); d2.remove(r+c)
    dfs(0); return res
Common Pitfalls
Watch out for these common mistakes
  • Forgetting to backtrack (undo)
  • Duplicate handling
  • Missing pruning
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(b^d)

Exponential in depth.

Space Complexity
O(d)

Recursion depth.

Ready to test your knowledge?

Test your pattern recognition with interactive questions