CodeMosa

Master LeetCode Patterns

BeginnerAdvanced Patterns

Backtracking

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

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

What is Backtracking?

#
Definition:

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

Code Templates

#
Pick/skip, add/remove with backtracking; prune early using constraints and treat duplicates deterministically (ordering or used sets).
# Math & Bits Templates
def gcd(a,b):
    while b: a,b = b, a%b
    return a
def lcm(a,b): return a//gcd(a,b)*b
def powmod(a,n,mod):
    res=1; a%=mod
    while n:
        if n&1: res = (res*a)%mod
        a=(a*a)%mod; n//=2
    return res

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

Related Patterns

#
Fenwick Tree (Binary Indexed Tree)GreedyKMP AlgorithmMath & BitsRange QueriesSegment Tree

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