What is the Backtracking pattern?

The Backtracking pattern is a systematic approach to solving a class of coding interview problems. By recognizing the Backtracking structure, you can solve problems in optimal time complexity using proven techniques.

When should I use the Backtracking pattern?

Use the Backtracking pattern when the problem structure matches its recognition signals — typically when brute force would be O(n²) or worse, and the pattern reduces complexity to Exponential (varies).

What is the time complexity of Backtracking?

The Backtracking pattern typically runs in Exponential (varies) time and uses O(n) recursion depth space. The exact complexity depends on the specific sub-variant being applied.

Is Backtracking important for coding interviews?

Yes — the Backtracking pattern is frequently tested at FAANG companies and competitive engineering interviews. Mastering this pattern gives you a reliable framework to solve many problem variations quickly.

How do I practice the Backtracking pattern?

Start by studying the pattern's mental model and recognition signals on DSAPatterns, then practice the curated LeetCode problems below in order from Easy to Hard. Aim for pattern recognition before memorizing solutions.

← back to patterns

pattern / MEDIUM

Backtracking.

Build solutions incrementally and undo choices

complexity

time

Exponential (varies)

space

O(n) recursion depth

practice questions

browse and solve all 8 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Make a choice, recurse, undo the choice. Prune branches that violate constraints.

Backtracking explores all possible solutions by building them incrementally and abandoning paths that fail constraints.

when to use ✓

01Generate subsets
02Generate permutations
03N-Queens
04Sudoku solver
05Word search
06Combination sum

when not ✗

01Greedy works
02DP can solve it

04'

recognition signals

Generate all combinations/permutations/subsets

Constraint satisfaction

Path enumeration

Sudoku, N-Queens

SubsetsPermutationsCombinationsN-QueensSudokuWord search

05'

templates

python

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3   n = len(nums)
4   if n < k:
5      return 0
6   window_sum = sum(nums[:k])
7   max_sum = window_sum
8   for i in range(k, n):
9      window_sum += nums[i] - nums[i - k]
10      max_sum = max(max_sum, window_sum)
11   return max_sum

common mistakes

01Not undoing choices (not backtracking properly)
02Forgetting to handle duplicates
03Missing base case

interview tips

01Always draw the recursion tree
02Use the 'choose, explore, unchoose' template
03Sort input for combination problems

06'

practice this pattern

8 curated problems from LeetCode

See all

Generate Parentheses# · Backtracking

MEDIUM

Permutations# · Backtracking

MEDIUM

Subsets# · Backtracking

MEDIUM

Combination Sum# · Backtracking

MEDIUM

Combination Sum II# · Backtracking

MEDIUM

Letter Combinations of a Phone Number# · Backtracking

MEDIUM

Palindrome Partitioning# · Backtracking

MEDIUM

N-Queens# · Backtracking

HARD

07'

faq

← back to patterns

pattern / MEDIUM

Backtracking.

Build solutions incrementally and undo choices

complexity

time

Exponential (varies)

space

O(n) recursion depth

practice questions

browse and solve all 8 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Make a choice, recurse, undo the choice. Prune branches that violate constraints.

Backtracking explores all possible solutions by building them incrementally and abandoning paths that fail constraints.

when to use ✓

01Generate subsets
02Generate permutations
03N-Queens
04Sudoku solver
05Word search
06Combination sum

when not ✗

01Greedy works
02DP can solve it

04'

recognition signals

Generate all combinations/permutations/subsets

Constraint satisfaction

Path enumeration

Sudoku, N-Queens

SubsetsPermutationsCombinationsN-QueensSudokuWord search

05'

templates

python

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3   n = len(nums)
4   if n < k:
5      return 0
6   window_sum = sum(nums[:k])
7   max_sum = window_sum
8   for i in range(k, n):
9      window_sum += nums[i] - nums[i - k]
10      max_sum = max(max_sum, window_sum)
11   return max_sum