Backtracking
Backtracking is an algorithmic technique where we:
Make a choice → explore it → if it doesn't work, undo the choice → try another choice.
The easiest way to remember it:
Choose ↓ Explore ↓ Valid? / \ Yes No ↓ ↓ Continue Undo ↓ Try next
Backtracking is basically recursion + undoing choices.
1. Real-Life Example
Imagine you are in a maze.
You start at the entrance.
START ↓ → → → X DEAD END
You reach a dead end.
What do you do?
You go back to the previous position and try another path.
That's backtracking.
Choose path ↓ Explore ↓ Dead end? ↓ Go back ↓ Try another path
2. Why Do We Need Backtracking?
Some problems have many possible choices.
For example, suppose we have:
A B C
We want to generate all possible arrangements.
Possible answers:
ABC ACB BAC BCA CAB CBA
There are many possibilities.
Backtracking lets us systematically:
- Choose something.
- Continue.
- Undo the choice.
- Choose something else.
3. Backtracking and Recursion
Backtracking is strongly connected to the previous topic:
Recursion
A recursive function explores possibilities.
Backtracking
After exploring one possibility, we undo the decision and try another.
So:
Recursion + Decision making + Undo ↓ Backtracking
A common structure is:
void backtrack(...) { if (solution_found) { // save solution return; } for (each choice) { // Make choice backtrack(...); // Undo choice } }
The undo step is the heart of backtracking.
4. Simple Example: Generate Binary Strings
Let's generate all binary strings of length 3.
Each position has two choices:
0 1
Possible results:
000 001 010 011 100 101 110 111
We can use recursion.
#include <iostream> using namespace std; void generate(string current, int n) { if (current.length() == n) { cout << current << endl; return; } // Choose 0 generate(current + "0", n); // Choose 1 generate(current + "1", n); } int main() { generate("", 3); return 0; }
Output:
000 001 010 011 100 101 110 111
5. Understanding the Recursion Tree
For length 2:
"" / \ 0 1 / \ / \ 00 01 10 11
Each level represents a decision.
Level 0 → "" Level 1 → 0 / 1 Level 2 → 00 / 01 / 10 / 11
This is a decision tree.
Backtracking explores this tree.
6. The Most Important Example: Subsets
Suppose:
[1, 2, 3]
We want all subsets.
Possible subsets:
[] [1] [2] [3] [1,2] [1,3] [2,3] [1,2,3]
For every element, we have two choices:
Take it Don't take it
So:
[] / \ take 1 skip 1 / \ [1] [] / \ / \ take2 skip2 take2 skip2
This produces all subsets.
7. Subsets Using Backtracking
#include <iostream> #include <vector> using namespace std; void generateSubsets( vector<int>& nums, int index, vector<int>& current ) { if (index == nums.size()) { for (int x : current) { cout << x << " "; } cout << endl; return; } // Choose: include nums[index] current.push_back(nums[index]); generateSubsets(nums, index + 1, current); // Undo choice current.pop_back(); // Choose: don't include nums[index] generateSubsets(nums, index + 1, current); } int main() { vector<int> nums = {1, 2, 3}; vector<int> current; generateSubsets(nums, 0, current); return 0; }
8. Understand push_back() and pop_back()
This is the most important part of the code.
We do:
current.push_back(nums[index]);
That means:
Make the choice.
Then:
generateSubsets(...);
means:
Explore that choice.
Then:
current.pop_back();
means:
Undo the choice.
So:
push_back() ↓ MAKE CHOICE ↓ recursive call ↓ EXPLORE ↓ pop_back() ↓ UNDO CHOICE
This pattern appears everywhere in backtracking.
9. Example of the Undo Process
Suppose:
nums = [1, 2]
Initially:
current = []
Choose 1:
current = [1]
Choose 2:
current = [1,2]
We reached a solution.
Now return.
Undo 2:
current = [1]
Then try the other choice.
Eventually undo 1:
current = []
Then try without 1.
This is why it's called:
Backtracking
We go forward, then go back when necessary.
10. Permutations
Another famous backtracking problem is generating permutations.
For:
[1, 2, 3]
we want:
123 132 213 231 312 321
At each position, we can choose an unused element.
For example:
"" / | \ 1 2 3 / \ / \ / \ 12 13 21 23 31 32 | | | | | | 123 132 213 231 312 321
11. Permutations Using Backtracking
#include <iostream> #include <vector> using namespace std; void permutations( vector<int>& nums, vector<int>& current, vector<bool>& used ) { if (current.size() == nums.size()) { for (int x : current) { cout << x << " "; } cout << endl; return; } for (int i = 0; i < nums.size(); i++) { if (used[i]) { continue; } // Make choice used[i] = true; current.push_back(nums[i]); // Explore permutations(nums, current, used); // Undo choice current.pop_back(); used[i] = false; } } int main() { vector<int> nums = {1, 2, 3}; vector<int> current; vector<bool> used(nums.size(), false); permutations(nums, current, used); return 0; }
Output:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
12. The Backtracking Template
This is one of the most useful templates to remember:
void backtrack(...) { if (base_case) { // Store / print solution return; } for (each possible choice) { // 1. Make choice choose(); // 2. Explore backtrack(...); // 3. Undo choice undo(); } }
Remember:
CHOOSE ↓ EXPLORE ↓ UNDO ↓ NEXT CHOICE
13. N-Queens Problem
One of the most famous backtracking problems is N-Queens.
Problem:
Place
Nqueens on anN × Nchessboard so that no two queens attack each other.
For 4 × 4, one solution is:
. Q . . . . . Q Q . . . . . Q .
Q = Queen
. = Empty
Queens cannot share:
- Same row
- Same column
- Same diagonal
14. How Backtracking Solves N-Queens
We place queens row by row.
Row 1 ↓ Try column 1 ↓ Valid? ↓ Place queen ↓ Row 2 ↓ Try columns ↓ ...
If we reach a situation where no column works:
No valid position ↓ Remove previous queen ↓ Try another position
That's backtracking.
15. Sudoku
Backtracking is also commonly used to solve Sudoku.
Suppose a cell is empty.
Try:
1
Check if valid.
If valid:
Place 1 ↓ Move to next cell
If eventually the choice causes a problem:
Invalid ↓ Remove 1 ↓ Try 2
Then:
Try ↓ Check ↓ Continue ↓ Failure? ↓ Undo ↓ Try next
16. Maze Problem
A maze is another classic example.
Suppose:
S . # . # . # . . . . E
S = Start
E = End
# = Wall
At every position, we can try directions:
UP DOWN LEFT RIGHT
If a path reaches a dead end:
Dead end ↓ Go back ↓ Try another direction
This is backtracking.
17. Backtracking vs Recursion
They are not exactly the same.
Recursion
A function calls itself.
Function ↓ Function ↓ Function
Backtracking
A problem explores different choices and undoes choices.
Choose ↓ Recursion ↓ Explore ↓ Undo ↓ Next choice
Therefore:
Backtracking commonly uses recursion, but recursion itself is not necessarily backtracking.
For example:
factorial(5)
uses recursion but not backtracking.
While:
N-Queens Sudoku Permutations Subsets Maze
commonly use recursion + backtracking.
18. Backtracking vs Brute Force
These concepts are related but different.
Brute Force
Try every possibility.
Try A Try B Try C Try D ...
Backtracking
Stop exploring a possibility as soon as we know it cannot produce a solution.
For example:
Choice ↓ Invalid? ↓ YES ↓ STOP THIS BRANCH
This is called pruning.
19. Pruning
Pruning means:
Don't explore a branch that cannot lead to a valid solution.
Imagine:
Start / | \ A B C / \ / \ X X X X
Suppose we discover that everything under B is impossible.
Instead of exploring:
B ├── ... ├── ... ├── ... ├── ...
we simply stop:
B → INVALID → PRUNE
This can make backtracking much faster.
20. Time Complexity
Backtracking often has exponential or factorial complexity, because it may explore many possibilities.
For subsets:
n elements
Each element has two choices:
Take Don't take
Therefore:
Number of subsets = 2ⁿ
So generating all subsets takes approximately:
O(2ⁿ)
For permutations:
Number of permutations = n!
Therefore:
O(n!)
This is why backtracking can become expensive for large inputs.
But pruning can reduce the actual work significantly for many problems.
21. Important Backtracking Problems
You should eventually learn these:
Beginner
- Generate binary strings
- Generate subsets
- Sum of subsets
- Combination generation
Intermediate
- Permutations
- Combination Sum
- Letter combinations
- Rat in a Maze
- Generate parentheses
Advanced
- N-Queens
- Sudoku Solver
- Word Search
- Graph coloring
- Hamiltonian path
- Knight's Tour
22. A General Way to Solve Backtracking Problems
Whenever you see a backtracking problem, ask these questions:
Step 1 — What are my choices?
For example:
N-Queens → columns Sudoku → numbers 1-9 Maze → directions Permutations → unused elements
Step 2 — What makes a choice invalid?
Queen attacks another queen Sudoku violates a rule Maze hits a wall
Step 3 — What is the base case?
Usually:
Complete solution
Step 4 — What do I need to undo?
For example:
current.push_back(x);
then later:
current.pop_back();
Or:
used[i] = true;
then:
used[i] = false;
23. The Most Important Pattern
Memorize this:
void backtrack(...) { // Base case if (solution_complete) { save_solution(); return; } for (each choice) { if (choice_is_invalid) { continue; } // Choose make_choice(); // Explore backtrack(...); // Undo undo_choice(); } }
And mentally:
BACKTRACKING | ┌─────┴─────┐ ↓ ↓ CHOOSE CHECK ↓ EXPLORE ↓ Solution? / \ YES NO ↓ ↓ Save Undo ↓ Try next choice
🧠 Final Summary
| Concept | Meaning |
|---|---|
| Recursion | Function calls itself |
| Backtracking | Try choices and undo them |
| Choice | One possible decision |
| Constraint | Rule that must be satisfied |
| Base case | Solution is complete |
| Undo | Remove previous decision |
| Pruning | Stop an impossible branch |
| Call stack | Stores recursive calls |
The core idea:
MAKE CHOICE ↓ RECURSE ↓ EXPLORE ↓ ┌───────┴───────┐ ↓ ↓ Success Failure ↓ ↓ Continue UNDO ↓ Try next choice
And the most important connection from your roadmap is:
Recursion ↓ Backtracking ↓ Trees / Graphs ↓ Divide & Conquer ↓ Dynamic Programming