Backtracking

Sometimes a problem doesn't have one obvious path to the answer. We may need to try different possibilities, and if one possibility doesn't work, we go back and try another.

This is the basic idea behind backtracking.

Backtracking is an algorithmic technique where we build a solution step by step, and whenever we realize that the current choice cannot lead to a valid solution, we undo that choice and try something else.

A simple way to remember it is:

Try → Check → If wrong, go back → Try another option

A Real-Life Example

Imagine you're walking through a maze.

You start at the entrance and choose a path.

Start
  ↓
Path A
  ↓
Dead end ❌

You can't continue, so you go back to the previous point and try another path.

Start
  ↓
Path A ❌
  ↩
Path B
  ↓
Path C
  ↓
Exit ✅

That's exactly what backtracking does.

It tries a possible solution, and if that solution doesn't work, it goes back and makes a different choice.

Backtracking and Recursion

Backtracking is closely related to recursion.

In fact, recursion is often used to implement backtracking.

The general structure looks something like this:

void solve() {

    for (each possible choice) {

        if (choice is valid) {

            make the choice;

            solve();

            undo the choice;
        }
    }
}

The important part is:

make the choice;
solve();
undo the choice;

That last step is what makes backtracking different from simply exploring possibilities.

A Simple Example

Suppose John has three different colors:

Red
Blue
Green

We want to generate all possible ways to choose two colors.

We can make a choice, continue building the solution, and then undo the choice so we can try another one.

For example:

Choose Red
   ↓
Choose Blue
   ↓
[Red, Blue]

Go back
   ↓
Choose Green
   ↓
[Red, Green]

Go back
   ↓
Choose Blue
   ↓
...

The algorithm keeps exploring possibilities until all valid combinations are found.

The Basic Backtracking Pattern

A typical backtracking solution has three steps.

1. Make a Choice

We choose one of the available options.

For example:

path.add(choice);

2. Explore

We recursively continue with that choice:

backtrack(...);

3. Undo the Choice

After exploring that possibility, we remove the choice:

path.remove(path.size() - 1);

This allows us to try a different choice.

So the pattern becomes:

Choose
  ↓
Explore
  ↓
Undo
  ↓
Try another choice

Example: Generate All Subsets

Let's look at a common backtracking problem.

Suppose we have:

[1, 2, 3]

We want to generate all possible subsets.

The answer is:

[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

For every number, we have two choices:

Take the number
        OR
Don't take the number

This naturally creates a decision tree.

                 []
              /      \
            [1]       []
           /   \      /  \
        [1,2] [1]   [2]  []

The process continues until we've considered every number.

Implementing Subsets in Java

We can solve this using backtracking:

import java.util.ArrayList;
import java.util.List;

class Main {

    static void generateSubsets(
            int[] numbers,
            int index,
            List<Integer> current) {

        if (index == numbers.length) {
            System.out.println(current);
            return;
        }

        // Include the current number
        current.add(numbers[index]);

        generateSubsets(numbers, index + 1, current);

        // Undo the choice
        current.remove(current.size() - 1);

        // Don't include the current number
        generateSubsets(numbers, index + 1, current);
    }

    public static void main(String[] args) {

        int[] numbers = {1, 2, 3};

        generateSubsets(
            numbers,
            0,
            new ArrayList<>()
        );
    }
}

The output will contain all possible subsets.

The important line to notice is:

current.remove(current.size() - 1);

This is the backtracking step.

We added a number, explored that possibility, and then removed it so we could explore another possibility.

Why Do We Undo the Choice?

This is probably the most important idea in backtracking.

Suppose our current path is:

[1, 2]

We explore what happens if we add 3:

[1, 2, 3]

Once we've finished exploring that possibility, we need to return to:

[1, 2]

so that we can try another option.

If we don't remove 3, our next solution would incorrectly continue using it.

So:

Add choice
   ↓
Explore
   ↓
Remove choice
   ↓
Try another choice

This is why backtracking is sometimes described as "making a choice, exploring it, and undoing it."

Backtracking vs Recursion

These two concepts are related, but they aren't exactly the same.

Recursion means a function calls itself.

Backtracking is a problem-solving technique where we explore choices and undo them when necessary.

Backtracking often uses recursion, but not every recursive algorithm is a backtracking algorithm.

For example, calculating factorial recursively:

factorial(n - 1);

uses recursion, but there's no decision or choice that we're undoing.

In backtracking, we usually have something like:

Choose
↓
Explore
↓
Undo

Pruning

Backtracking can become very expensive because it may have to explore many possibilities.

To improve it, we can sometimes stop exploring a path as soon as we know it cannot produce a valid solution.

This is called pruning.

Imagine you're solving a maze.

If you enter a path and immediately discover that it leads to a dead end, there's no reason to continue exploring that path.

So you stop early and go back.

Path
 ↓
Invalid ❌
 ↓
Stop exploring
 ↓
Backtrack

This can significantly reduce the amount of work.

Example: Choosing Numbers

Suppose we want to find combinations whose sum is exactly 5.

Given:

[2, 3, 4]

We could try:

2
 ↓
3
 ↓
2 + 3 = 5 ✅

But suppose we reach:

2 + 4 = 6

If we're only interested in sums of 5, there's no point continuing down that path.

We can stop and backtrack.

This is an example of pruning.

Common Backtracking Problems

Once you understand the basic idea, you'll start seeing backtracking in many classic DSA problems.

Some common examples are:

• Generate all subsets

• Generate all permutations

• Generate combinations

• N-Queens problem

• Sudoku solver

• Maze solving

• Rat in a Maze

• Word Search

• Combination Sum

These problems look very different on the surface, but many of them follow the same basic pattern:

Choose
  ↓
Check
  ↓
Explore
  ↓
Undo
  ↓
Try another choice

Backtracking and a Maze

Let's imagine a simple maze:

S . . #
# . . .
# # . E

S is the starting point and E is the destination.

The algorithm can try moving:

Up
Down
Left
Right

At every position, it chooses a possible direction.

If it reaches a blocked path:

Blocked ❌

it goes back.

If it reaches the destination:

Success ✅

This is one of the most intuitive examples of backtracking.

Time Complexity

Backtracking can be expensive because it may need to explore many possible combinations.

For example, when generating all subsets of n elements, every element has two choices:

Include it
    OR
Don't include it

So there can be:

2ⁿ

possible subsets.

Therefore, the number of possibilities grows exponentially.

That's why backtracking algorithms can often have exponential time complexity, such as:

O(2ⁿ)

or even larger depending on the problem.

However, pruning can reduce the actual amount of work significantly in many practical cases.

The Main Idea

Backtracking is basically about exploring possibilities and going back when a choice doesn't work.

The pattern to remember is:

Make a choice
      ↓
Explore the choice
      ↓
Is it valid?
   ↙       ↘
 Yes       No
  ↓         ↓
Continue   Backtrack
  ↓
Undo choice
  ↓
Try another choice

The most important part is the undo step.

Backtracking = Try a choice → Explore → Undo the choice → Try another possibility.

Once you understand this pattern, problems like subsets, permutations, combinations, Sudoku, N-Queens, and maze solving become much easier to approach.