Ugenz Academy/Tutorial

Backtracking

10 min read1,920 words

Reading progress

Keep learning

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:

  1. Choose something.
  2. Continue.
  3. Undo the choice.
  4. 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 N queens on an N × N chessboard 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

ConceptMeaning
RecursionFunction calls itself
BacktrackingTry choices and undo them
ChoiceOne possible decision
ConstraintRule that must be satisfied
Base caseSolution is complete
UndoRemove previous decision
PruningStop an impossible branch
Call stackStores 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy