Backtracking
The Backtracking Pattern
Build a candidate solution one choice at a time. Recurse after each choice, and if the branch cannot lead to a valid answer, undo the choice and try the next. The undo step is what separates backtracking from plain recursion.
Interactive problems
Free to open
How do you recognise a backtracking problem?
The problem asks for all permutations, all subsets, all combinations, or all ways of doing something — or it is a constraint puzzle like N-Queens or Sudoku. "Find every…" means backtracking.
What is the time complexity of the backtracking pattern?
Exponential by nature — O(2ⁿ) for subsets, O(n!) for permutations. Pruning invalid branches early is the only meaningful optimisation.
Backtracking practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Backtracking problems by difficulty and complexity
The difficulty, running time and extra space of every backtracking solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Introduction to Backtracking | Medium | Ω(n × 2ⁿ) | Θ(n × 2ⁿ) | O(n × 2ⁿ) | O(n) path, O(n × 2ⁿ) output |
| Solution Space Trees | Medium | Ω(n × 2ⁿ) | Θ(n × 2ⁿ) | O(n × 2ⁿ) | O(n) depth, O(n × 2ⁿ) output |
| Subsets (Power Set) | Medium | Ω(n × 2ⁿ) | Θ(n × 2ⁿ) | O(n × 2ⁿ) | O(n) depth, O(n × 2ⁿ) output |
| Combination Sum | Medium | O(n log n) | O(n^(T/m + 1)) | O(n^(T/m + 1)) | O(T/m) depth |
| Generate Parentheses | Medium | Ω(4ⁿ / √n) | Θ(4ⁿ / √n) | O(4ⁿ / √n) | O(n) depth, O(4ⁿ / √n) output |
| Word Search | Medium | O(m × n) | O(m × n × 3ᴸ) | O(m × n × 3ᴸ) | O(L) stack |
Related patterns and concepts
The underlying technique is covered from first principles in the backtracking lesson in the DSA visualizer curriculum. Backtracking is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree