Why should you care?
Many problems don't have an obvious single correct choice.
Instead, you have multiple possibilities:
Choice A
Choice B
Choice C
...
You need to explore those possibilities and find a valid or optimal solution.
Examples include:
- Solving Sudoku
- N-Queens
- Generating permutations
- Generating combinations
- Maze solving
- Subset problems
- Constraint satisfaction
- Word search
- Puzzle solving
Trying every possibility blindly can be extremely expensive.
Backtracking gives us a structured way to explore possibilities:
Make a choice, explore it, and if it doesn't work, undo it and try another choice.
This simple idea is one of the most powerful patterns in algorithmic problem solving.
The Problem
Suppose you want to generate all permutations of:
[1, 2, 3]
The possible permutations are:
123
132
213
231
312
321
How can we systematically generate them?
We can build the answer one element at a time.
Start:
[]
Choose 1:
[1]
Choose 2:
[1, 2]
Choose 3:
[1, 2, 3]
We found one solution.
Now we undo the last decision:
[1, 2]
Try another choice:
[1, 3]
Then:
[1, 3, 2]
And continue.
This process of making and undoing choices is called backtracking.
The Concept
Backtracking explores a decision tree.
At every step:
Choose
↓
Explore
↓
Valid?
├── Yes → Continue
└── No → Undo
↓
Try another choice
The general pattern is:
backtrack(state):
if solution is complete:
process solution
return
for each possible choice:
make choice
if choice is valid:
backtrack(new state)
undo choice
The most important operation is:
undo choice
That is where the name backtracking comes from.
Simple Explanation
Imagine trying to find a path through a maze.
You walk:
Start
↓
A
↓
B
↓
C
Suppose C is a dead end.
You don't start from the beginning.
You go backward:
C
↑
B
Then try another path:
B
↓
D
↓
E
This is exactly what a backtracking algorithm does.
Try
↓
Dead end?
↓
Go back
↓
Try another path
The algorithm explores the search space while abandoning choices that cannot lead to a valid solution.
Real-world Analogy
Imagine you are trying to unlock a combination lock.
Suppose each position can contain:
0–9
You try:
1
↓
3
↓
7
If the combination doesn't work, you go back:
1 → 3 → 7
↑
Undo
Then:
1 → 3 → 8
If that fails:
1 → 4 → ...
You systematically explore possibilities.
That's backtracking.
Code Example
Let's generate all permutations of an array.
Step 1: Start with an empty path
[]
Step 2: Choose an element
[1]
Step 3: Choose another
[1, 2]
Step 4: Complete the permutation
[1, 2, 3]
Then we undo:
[1, 2]
and try:
[1, 3]
Let's implement it.
import java.util.*;
public class Main {
static void generatePermutations(
int[] nums,
boolean[] used,
List<Integer> current) {
// Complete permutation
if (current.size() == nums.length) {
System.out.println(current);
return;
}
for (int i = 0; i < nums.length; i++) {
// Already used
if (used[i]) {
continue;
}
// Make choice
used[i] = true;
current.add(nums[i]);
// Explore
generatePermutations(nums, used, current);
// Undo choice
current.remove(current.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
boolean[] used = new boolean[nums.length];
generatePermutations(
nums,
used,
new ArrayList<>()
);
}
}
Output:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
How the Code Works
The key lines are:
used[i] = true;
current.add(nums[i]);
We make a choice.
Then:
generatePermutations(nums, used, current);
We explore the choice.
Finally:
current.remove(current.size() - 1);
used[i] = false;
We undo the choice.
This is the fundamental backtracking pattern:
Make
↓
Explore
↓
Undo
You should recognize this pattern immediately when reading backtracking code.
Visualizing the Decision Tree
For:
[1, 2, 3]
The search tree looks approximately like:
[]
/ | \
1 2 3
/ \ / \ / \
2 3 1 3 1 2
| | | | | |
3 2 3 1 2 1
Each root-to-leaf path represents one permutation.
For example:
[] → 1 → 2 → 3
produces:
123
Backtracking explores this tree using recursion.
Common Mistakes
Mistake 1: Forgetting to undo the choice
Consider:
current.add(nums[i]);
generatePermutations(...);
// Missing undo
If you don't remove the element afterward, the state becomes corrupted.
You need:
current.add(nums[i]);
generatePermutations(...);
current.remove(current.size() - 1);
The undo operation is essential.
Mistake 2: Confusing backtracking with recursion
Backtracking usually uses recursion, but recursion alone does not mean backtracking.
For example:
factorial(n)
uses recursion.
But it doesn't explore multiple choices and undo them.
Backtracking generally looks like:
Choice
↓
Recursive exploration
↓
Undo
↓
Next choice
So:
Backtracking is a problem-solving technique that often uses recursion as its implementation mechanism.
Mistake 3: Exploring invalid paths unnecessarily
Suppose you're solving a maze and you know:
This path already violates a constraint.
There is no reason to continue exploring it.
Instead:
Invalid state
↓
Stop exploring
↓
Backtrack
This is called pruning.
Pruning can dramatically reduce the search space.
Advanced Notes
1. The Backtracking Template
Most backtracking problems can be expressed using this structure:
void backtrack(State state) {
if (isComplete(state)) {
saveSolution(state);
return;
}
for (Choice choice : choices(state)) {
if (!isValid(choice, state)) {
continue;
}
makeChoice(choice, state);
backtrack(state);
undoChoice(choice, state);
}
}
When you encounter a new backtracking problem, try mapping it to these four operations:
1. What are my choices?
2. What makes a choice valid?
3. When is the solution complete?
4. How do I undo a choice?
2. Pruning
Without pruning:
Explore everything
With pruning:
Explore
↓
Invalid?
↓
STOP
For example, suppose you are finding subsets whose sum equals 10.
Current path:
2 + 7 + 8 = 17
If all remaining numbers are positive, we already exceeded the target.
There is no point continuing.
We can immediately backtrack.
This is pruning.
3. N-Queens Problem
The N-Queens problem asks:
Can we place N queens on an N × N chessboard so that no two queens attack each other?
For four queens:
. Q . .
. . . Q
Q . . .
. . Q .
A queen attacks:
Same row
Same column
Diagonal
A backtracking solution works row by row.
Place queen
↓
Is position safe?
├── No → Try next position
└── Yes
↓
Move to next row
↓
Continue
↓
Dead end?
↓
Remove queen
↓
Try another position
This is a classic example of backtracking with pruning.
4. Sudoku
Sudoku is another classic backtracking problem.
Choose an empty cell:
↓
Try 1
↓
Valid?
├── No → Try 2
└── Yes
↓
Next cell
↓
Eventually invalid?
↓
Undo
↓
Try another number
The algorithm systematically searches possible assignments while immediately abandoning invalid states.
5. Subsets
For every element, we can make two choices:
Take it
OR
Don't take it
For:
[1, 2, 3]
The decision tree begins:
[]
/ \
Take Skip
1 1
/ \ / \
2 skip 2 skip
This pattern appears in many problems involving:
- Subsets
- Combinations
- Target sums
- Partitioning
- Selection
A useful mental pattern is:
Element
/ \
Take Skip
6. Combinations
Suppose we want all combinations of size 2 from:
[1, 2, 3, 4]
The results are:
[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]
Unlike permutations, order doesn't matter.
Backtracking maintains a starting index:
static void combinations(
int[] nums,
int start,
int k,
List<Integer> current) {
if (current.size() == k) {
System.out.println(current);
return;
}
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
combinations(
nums,
i + 1,
k,
current
);
current.remove(current.size() - 1);
}
}
The important difference is:
Permutations → can choose previous elements again
Combinations → move forward through the array
7. Word Search
Consider a character grid:
A B C
D E F
G H I
Suppose we want to find:
"BEH"
We can:
B
↓
E
↓
H
If a path doesn't match the word:
Stop
↓
Undo
↓
Try another direction
Backtracking is particularly useful when exploring paths through grids.
8. Backtracking and DFS
Backtracking is closely related to Depth-First Search.
DFS explores:
Go deep
↓
Explore
↓
Return
↓
Explore another branch
Backtracking adds a crucial idea:
Make a decision
↓
Explore
↓
Undo the decision
You can think of many backtracking algorithms as:
DFS over a decision tree + state modification + undoing choices.
This connects directly to the DFS concept you learned earlier.
9. Backtracking and Dynamic Programming
Backtracking and Dynamic Programming can solve some similar-looking problems, but they have different strategies.
Backtracking:
Try possibilities
↓
Reject invalid paths
↓
Continue exploring
Dynamic Programming:
Identify repeated subproblems
↓
Solve each once
↓
Store results
↓
Reuse them
For example:
Backtracking
↓
Explore search tree
↓
Potentially exponential
Whereas:
Dynamic Programming
↓
Merge repeated states
↓
Avoid repeated computation
An important optimization is that memoization can sometimes be added to a backtracking-style search when different paths reach the same state.
10. Time Complexity
Backtracking algorithms are often exponential.
For permutations of n elements:
n!
possible solutions exist.
Therefore, generating all permutations requires at least:
O(n!)
time just to output them.
For subset generation:
2^n
subsets exist.
So the search space is:
O(2^n)
For N-Queens, the exact complexity is more complicated, but a straightforward backtracking solution has exponential search behavior.
The key lesson:
Backtracking is not necessarily fast because it is clever; it is fast because it avoids exploring branches that can be proven useless.
11. Branch and Bound
A related optimization technique is Branch and Bound.
Backtracking usually asks:
"Is this state valid?"
Branch and Bound can additionally ask:
"Can this branch possibly produce a better solution?"
If not:
Prune the branch.
This is especially useful for optimization problems.
12. How to Recognize a Backtracking Problem
Look for problems containing phrases such as:
"Generate all..."
"Find all..."
"List every possible..."
"Can we arrange..."
"Find a valid configuration..."
"Choose or don't choose..."
"Try every possibility..."
Then ask:
What are my choices?
For example:
N-Queens:
Which column should I place the queen in?
Sudoku:
Which number should go here?
Permutations:
Which unused element should I choose?
Subset:
Should I take this element or skip it?
Maze:
Which direction should I move?
If each decision creates more decisions, you likely have a decision tree.
That is where backtracking becomes useful.
The Bigger Picture
Your algorithmic progression is now becoming much more powerful:
Data Structures
↓
Searching
↓
Sorting
↓
DFS / BFS
↓
Greedy Algorithms
↓
Dynamic Programming
↓
Backtracking
These techniques solve problems in fundamentally different ways.
Greedy
Make the best choice now.
Dynamic Programming
Solve states and reuse their answers.
Backtracking
Explore choices and undo bad decisions.
A useful comparison:
| Technique | Main Idea |
|---|---|
| Greedy | Commit to a provably safe local choice |
| DP | Store results of overlapping subproblems |
| Backtracking | Explore possibilities and undo choices |
| DFS | Explore a graph/tree deeply |
| Divide & Conquer | Split into independent subproblems |
Backtracking also connects several concepts you've already learned:
Recursion
+
DFS
+
Decision Trees
+
Pruning
+
State Management
↓
Backtracking
The Most Important Mental Model
Remember this:
MAKE
↓
EXPLORE
↓
VALID?
├── YES → Continue
└── NO → Stop
↓
UNDO
↓
TRY NEXT
Or in one sentence:
Backtracking is controlled trial and error: make a choice, explore it, and undo it when it cannot lead to a solution.
Once you can identify the choice, constraint, base case, and undo operation, many backtracking problems become much easier to structure.
Summary
Backtracking is an algorithmic technique for exploring a large set of possible solutions systematically.
Key ideas:
- Backtracking explores a decision tree.
- It makes a choice and recursively explores it.
- It undoes the choice before trying another possibility.
- Recursion is commonly used to implement backtracking.
- Invalid states should be rejected as early as possible.
- Pruning prevents unnecessary exploration.
- Permutations, combinations, subsets, Sudoku, N-Queens, and maze solving are classic applications.
- Backtracking is closely related to DFS.
- Backtracking and Dynamic Programming solve problems differently.
- Memoization can sometimes optimize repeated states in a search.
- Many backtracking problems have exponential or factorial search spaces.
- The quality of pruning can have a major impact on practical performance.
Top comments (0)