What Is Backtracking?

Backtracking is a systematic way to explore all possible solutions and abandon paths that can't lead to a valid answer. Think of navigating a maze: you walk forward, hit a dead end, go back to the last fork, and try another path.

🧩
The maze analogy
Go forward, hit a wall, backtrack, try another direction

Imagine you're solving a Sudoku puzzle. You place a number in an empty cell, move to the next cell, and keep going. The moment you realize a placement violates the rules, you erase it (backtrack) and try a different number. That's backtracking: make a choice, explore it fully, and undo it if it doesn't work.

Backtracking is essentially a depth-first search over a decision tree. At each step you make a choice, recurse deeper, and — if the path fails — you undo the choice and try the next option. The "undo" step is what makes it backtracking, not just plain recursion.

When brute force meets intelligence:
Backtracking doesn't blindly try every combination. It prunes branches early — if a partial solution already violates a constraint, it abandons that entire subtree. This pruning is what makes backtracking practical for problems that would otherwise be exponential.

The Template: Choose → Explore → Unchoose

Every backtracking problem follows the same three-step pattern. Once you recognise it, you can solve dozens of interview problems by adapting this skeleton:

backtrack_template.py The universal backtracking skeleton

Breaking it down

  • Base case — Check if path is a complete solution. If yes, save it and return.
  • Choose — Pick a candidate and add it to the current path.
  • Explore — Recurse with the updated path to go deeper.
  • Unchoose — Remove the last choice (path.pop()) so you can try the next candidate. This is the backtracking step.
Why path[:] and not just path?
Lists are mutable in Python. If you append path directly, every entry in result points to the same list — which ends up empty after all the pop() calls. path[:] creates a snapshot (shallow copy) at the moment you found a solution.

Decision Tree for Permutations of [1, 2, 3]

Every backtracking algorithm builds a decision tree. Each node represents a partial solution; each branch represents a choice. Leaf nodes are complete permutations. Pruned branches (red, dashed) are paths we skip because the element was already used.

Permutations Decision Tree — [1, 2, 3]

[ ] [1] [2] [3] [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 1 2 3
Partial solution Complete permutation (leaf) Pruned (duplicate element)

At each level, we pick from the remaining elements. If an element is already in the path, we prune that branch. The 6 green leaf nodes are the 6 permutations of [1, 2, 3] — which is 3! = 6.

Problem: Permutations

Given a list of distinct integers, return all possible permutations. This is LeetCode 46 and one of the most common backtracking interview problems.

Approach: At each level of recursion, choose one element from the remaining pool. When the remaining pool is empty, you have a complete permutation.

permutations.py O(n! * n) time, O(n) space
Output
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Walk-through

  1. Start: path=[], remaining=[1,2,3]
  2. Choose 1: path=[1], remaining=[2,3]
  3. Choose 2: path=[1,2], remaining=[3]
  4. Choose 3: path=[1,2,3], remaining=[] — save!
  5. Unchoose 3: path=[1,2] — back to step 3, no more choices
  6. Unchoose 2: path=[1] — now choose 3 instead
  7. Choose 3: path=[1,3], remaining=[2]
  8. Choose 2: path=[1,3,2] — save! ... and so on
Complexity:
There are n! permutations, and copying each one takes O(n) time. So total time is O(n! * n). The recursion depth is O(n), and each level creates a new remaining list of size up to n, so space is O(n^2) in the call stack.

Problem: Subsets

Given a list of distinct integers, return all possible subsets (the power set). This is LeetCode 78. Unlike permutations, order doesn't matter — [1,2] and [2,1] are the same subset.

Key difference: We record every partial path as a valid subset (not just complete ones). We use a start index to avoid duplicates — once we've passed an element, we don't go back to it.

subsets.py O(2^n * n) time, O(n) space
Output
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

How subsets differs from permutations

  • Permutations: Save only when remaining is empty (all elements used). Order matters.
  • Subsets: Save at every node of the tree, including the empty path. Use start to ensure we only pick elements ahead of the current position, avoiding duplicates like [2,1] when we already have [1,2].
Complexity:
There are 2^n subsets (each element is either included or not). Copying each takes O(n), so total is O(2^n * n). The recursion depth is O(n).

Problem: N-Queens (Simplified)

Place N queens on an N x N chessboard so that no two queens attack each other. Queens can attack along rows, columns, and diagonals. This is LeetCode 51 and the classic constraint satisfaction problem.

Strategy: Place one queen per row. For each row, try every column. Before placing, check that no existing queen shares the same column or diagonal. If no valid column exists for a row, backtrack to the previous row.

4-Queens Solution — One Valid Configuration

♛
♛
♛
♛
Queens at positions: (0,1), (1,3), (2,0), (3,2) — no two share a row, column, or diagonal.
n_queens.py Count solutions for N-Queens
Output
[1, 3, 0, 2] [2, 0, 3, 1] 2 solutions for 4-Queens
The pruning power:
A brute-force approach would try all n^n placements. Backtracking with column and diagonal checks reduces this dramatically. For 8-Queens, brute force would check 16 million+ placements; backtracking finds all 92 solutions while exploring only a tiny fraction of that search space.

When to Use Backtracking

Backtracking is the right tool when a problem asks you to enumerate all valid configurations or find any valid configuration under constraints. Here's a quick checklist:

🎯
Pattern recognition
Spot these keywords in interview problems
  • Permutations — "Generate all orderings of..." (LeetCode 46)
  • Combinations / Subsets — "Find all subsets / combinations that sum to..." (LeetCode 78, 39, 40)
  • Constraint satisfaction — Sudoku solver, N-Queens, crossword puzzles
  • Path finding with constraints — "Find all paths from source to target" (LeetCode 797)
  • String partitioning — "Partition into palindromes" (LeetCode 131)
  • Word search / letter board — "Find a word in a grid" (LeetCode 79)

Backtracking vs. Dynamic Programming

If the problem asks for all solutions, use backtracking. If it asks for the count or optimal value (min/max), DP might be better. Many problems can be solved with either — but backtracking enumerates, while DP optimises.

Interview tip:
When an interviewer says "generate all..." or "find every valid...", that's your cue for backtracking. Start with the Choose-Explore-Unchoose template, then figure out the constraint check (is_valid) and the base case (is_solution).

Try It Yourself

Generate All Permutations

Write a function permutations(nums) that returns all permutations of the input list. Use the Choose-Explore-Unchoose pattern.

Challenge

Combination Sum
Your task:

Given a list of distinct positive integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be used unlimited times. This is LeetCode 39.

Example: candidates = [2, 3, 6, 7], target = 7 should return [[2, 2, 3], [7]].

Hint structure: Use the subsets pattern with a start index, but instead of advancing past the current element, allow re-picking it by passing i (not i + 1) when you recurse. Add a pruning check: if the running sum exceeds the target, stop exploring.

Start with backtrack(start, path, current_sum). Base case: if current_sum == target, save the path. Loop from start to len(candidates). For each candidate, if current_sum + candidates[i] <= target, append it to path, recurse with i (same index, allowing reuse), then pop. The start index prevents [3,2,2] appearing alongside [2,2,3].

Quiz

Question 1 of 5
What are the three steps in the backtracking template?
Question 2 of 5
In the permutations problem, why do we use path[:] instead of path when saving a result?
Question 3 of 5
How does the subsets algorithm avoid generating duplicate subsets like [2,1] and [1,2]?
Question 4 of 5
In the N-Queens solution, what three sets are used to check if a queen placement is safe?
Question 5 of 5
When should you prefer backtracking over dynamic programming?
0
/5
Great work! You understand backtracking.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

You've learned to explore every possibility.
Now explore every career opportunity.

Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.

Explore our AI-era courses →