Cheatsheet›Backtracking

CORE PATTERNHigh Frequency

Backtracking

Backtracking is an algorithmic technique that explores all possible solutions by building candidates incrementally and abandoning ('backtracking from') a candidate the moment it is determined it cannot lead to a valid solution. It is a controlled form of brute-force that prunes the search space using constraints.

TimeO(N! or 2^N or N^K) — problem dependent

SpaceO(N) — recursion depth

DifficultyMedium to Hard

Key Insight

Choose, explore, un-choose — prune every dead branch early.

Flip ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEBacktracking

Click anywhere to flip back ⟲

Recognition Signals (When to use this pattern)

→Generate all subsets, permutations, or combinations
→Find all valid arrangements satisfying constraints
→N-Queens, Sudoku, or grid path counting
→Word search or sequence matching on a grid
→Partition or split an input into valid segments
→Return all solutions, not just one optimal value

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

Subsets / Power Set

At each index, decide include or exclude — 2^N total subsets.

Common Problems

• Subsets
• Subsets II (with duplicates)
• Letter Case Permutation
• Find All Subsets of Size K
• Beautiful Arrangement II

5 problems

Combinations

Choose exactly k elements — prune branches that can't reach k early.

Common Problems

• Combinations
• Combination Sum
• Combination Sum II
• Combination Sum III
• Factor Combinations

5 problems

Permutations

Every ordering of elements — use a 'used' array to track which elements are in the current path.

Common Problems

• Permutations
• Permutations II (with duplicates)
• Next Permutation
• Permutation Sequence
• Beautiful Arrangement

5 problems

Grid / Word Search

DFS on a 2D grid — mark cells visited in-place, restore on backtrack.

Common Problems

• Word Search
• Word Search II
• Unique Paths III
• N-Queens (grid placement)
• Sudoku Solver

5 problems

N-Queens / Constraint Placement

Place items row by row — use sets to check column and diagonal conflicts in O(1).

Common Problems

• N-Queens
• N-Queens II
• Sudoku Solver
• Beautiful Arrangement
• 24 Game

5 problems

String Partition / Palindrome

Partition a string at every valid cut — prune immediately when the prefix is invalid.

Common Problems

• Palindrome Partitioning
• Restore IP Addresses
• Word Break II
• Generate Parentheses
• Decode Ways II

5 problems

Template / Approach

Template for: Subsets / Power Set

Start with Empty Subset

Record the current partial subset at every call — not just at leaves. The empty set is always a valid subset.

Iterate from Start Index

Loop from 'start' to end of the array. Passing 'start' avoids choosing the same element twice and prevents duplicate subsets.

Include → Recurse → Exclude

Push the element, recurse with start = i+1, then pop the element. This is the canonical backtrack undo.

template_cpp

💡 Universal subset skeleton. Record result at every node (not just leaves) to capture subsets of every size. Pass start = i+1 to avoid reusing earlier elements.

1// Subsets — include/exclude at every index
2vector<vector<int>> result;
3vector<int> current;
4 
5void backtrack(vector<int>& nums, int start)
6{
7   result.push_back(current);   // record subset at every node
8 
9   for (int i = start; i < (int)nums.size(); i++)
10   {
11      current.push_back(nums[i]);      // choose
12      backtrack(nums, i + 1);           // explore (no reuse)
13      current.pop_back();               // un-choose
14   }
15}
16 
17vector<vector<int>> subsets(vector<int>& nums)
18{
19   backtrack(nums, 0);
20   return result;
21}

Key Idea:Record the result at every recursion node (not just leaves) to capture all subset sizes. The 'start' index enforces a forward-only scan — no element is reused. For duplicates: sort first, then skip nums[i] == nums[i-1] when i > start (same level, not a child call).

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Medium

Subsets

LeetCode #78

Medium

Subsets II

LeetCode #90

Medium

Letter Case Permutation

LeetCode #784

Medium

Find All Subsets That Sum to Target

LeetCode #

Medium

Combinations

LeetCode #77

Medium

Combination Sum

LeetCode #39

Medium

Combination Sum II

LeetCode #40

Medium

Combination Sum III

LeetCode #216

Medium

Factor Combinations

LeetCode #254

Medium

Permutations

LeetCode #46

Medium

Permutations II

LeetCode #47

Hard

Permutation Sequence

LeetCode #60

Medium

Beautiful Arrangement

LeetCode #526

Medium

Word Search

LeetCode #79

Hard

Word Search II

LeetCode #212

Hard

Unique Paths III

LeetCode #980

Hard

Sudoku Solver

LeetCode #37

Hard

N-Queens

LeetCode #51

Hard

N-Queens II

LeetCode #52

Hard

24 Game

LeetCode #679

Medium

Palindrome Partitioning

LeetCode #131

Medium

Restore IP Addresses

LeetCode #93

Medium

Generate Parentheses

LeetCode #22

Hard

Word Break II

LeetCode #140

Hard

Palindrome Partitioning II

LeetCode #132

Backtracking

1// Subsets — include/exclude at every index

2vector<vector<int>> result;

3vector<int> current;

5void backtrack(vector<int>& nums, int start)

7 result.push_back(current); // record subset at every node

9 for (int i = start; i < (int)nums.size(); i++)

10 {

11 current.push_back(nums[i]); // choose

12 backtrack(nums, i + 1); // explore (no reuse)

13 current.pop_back(); // un-choose

14 }

15}

17vector<vector<int>> subsets(vector<int>& nums)

18{

19 backtrack(nums, 0);

20 return result;

21}