Introduction to Backtracking

Some problems ask you to find every possible answer. Make all the passwords of length 3. List all the ways to seat people. Pick every group you can form from a set. You cannot just guess one answer here. You have to try things. When a try goes wrong, you step back and try the next thing. That stepping back is the whole idea. It is called backtracking.

🧭 A maze tells the story best

Picture Riya standing at the start of a maze. She picks a path and walks. Then she hits a wall. So what does she do? She does not give up and go home. She walks back to the last spot where the path split into two. Then she takes the other turn she had not tried yet.

That walking back to the last choice point is backtracking. Backtracking means undoing your last move so you can try a different one.

So the rhythm is simple. Pick a turn. Walk forward. If you hit a wall, walk back. Pick a different turn. Keep doing this until you find the exit. Or until you have tried every path.

A computer does the exact same thing when it solves these problems. It just calls the choice points “states” and the walking back “returning from recursion”.

🎯 What backtracking really is

Backtracking is a way to search through all the choices a problem gives you, one step at a time. You build the answer piece by piece. At each step you make one choice. Then you go deeper and make the next choice. If the path you are on cannot work, you throw away the last choice and try another.

Here is the thing. It is just smart trial and error. You try. You check. You undo. You try again.

The pattern always runs in the same order:

• Choose — add one option to your current answer.
• Explore — go deeper and decide the rest by calling the function again. This is the recursion.
• Un-choose — remove that option so the spot is clean for the next option to try.

That last move is the one people forget. Un-choose is the “walk back to the split” part of the maze. Without it your answer keeps the old choice stuck inside it. Then everything after that goes wrong.

🌳 The decision tree

Every backtracking problem is really a decision tree. At each level you decide one thing. Each branch is one option. Walking down to a leaf gives you one complete answer.

Say you want every string of length 2 made of 0 and 1. At each spot you choose 0 or 1. Here is the tree of those choices.

See how every leaf at the bottom is one finished string? 00, 01, 10, 11. Backtracking walks down to a leaf, writes down the answer, then walks back up to the last split and goes down the next branch. That walk back up is the un-choose step.

🧩 A tiny example: all binary strings of length n

Let us build every binary string of length n. A binary string is just a string made only of the characters 0 and 1. For n equal to 2 the answers are 00, 01, 10, 11.

The plan reads straight off the maze idea. We keep a current string we are building. When it reaches length n, that is a finished answer. So we print it. Otherwise we have a choice to make for the next character.

Steps the function follows:

1. If the current string has length n, print it and return. This is reaching the maze exit.
2. Choose 0. Add it to the current string.
3. Explore. Call the function again to fill the rest.
4. Un-choose 0. Remove it so the spot is free.
5. Now do the same three moves for 1: choose, explore, un-choose.

Here is that idea in all five languages. Watch how each call adds one character, goes deeper, then removes it before trying the other character.

#include <stdio.h>
#include <string.h>

// current holds the string we are building, pos is the next empty spot
void generate(char *current, int pos, int n) {
    if (pos == n) {            // reached full length, this is one answer
        current[pos] = '\0';
        printf("%s\n", current);
        return;
    }
    current[pos] = '0';        // choose 0
    generate(current, pos + 1, n);  // explore
    // un-choose happens by overwriting below
    current[pos] = '1';        // choose 1
    generate(current, pos + 1, n);  // explore
}

int main(void) {
    int n = 2;
    char current[20];
    generate(current, 0, n);
    return 0;
}

00
01
10
11

#include <iostream>
#include <string>
using namespace std;

// current is the string built so far, n is the target length
void generate(string current, int n) {
    if ((int)current.size() == n) {  // full length, one answer is ready
        cout << current << "\n";
        return;
    }
    current.push_back('0');          // choose 0
    generate(current, n);            // explore
    current.pop_back();              // un-choose 0

    current.push_back('1');          // choose 1
    generate(current, n);            // explore
    current.pop_back();              // un-choose 1
}

int main() {
    int n = 2;
    generate("", n);
    return 0;
}

00
01
10
11

public class BinaryStrings {
    // current builds the string, n is the target length
    static void generate(StringBuilder current, int n) {
        if (current.length() == n) {   // full length, print one answer
            System.out.println(current.toString());
            return;
        }
        current.append('0');           // choose 0
        generate(current, n);          // explore
        current.deleteCharAt(current.length() - 1);  // un-choose 0

        current.append('1');           // choose 1
        generate(current, n);          // explore
        current.deleteCharAt(current.length() - 1);  // un-choose 1
    }

    public static void main(String[] args) {
        int n = 2;
        generate(new StringBuilder(), n);
    }
}

00
01
10
11

# current is the string built so far, n is the target length
def generate(current, n):
    if len(current) == n:      # full length, this is one answer
        print(current)
        return
    # choose 0, explore, then move on to the next choice
    generate(current + "0", n)
    # choose 1, explore
    generate(current + "1", n)

n = 2
generate("", n)

00
01
10
11

// current is the string built so far, n is the target length
function generate(current, n) {
  if (current.length === n) {   // full length, this is one answer
    console.log(current);
    return;
  }
  generate(current + "0", n);   // choose 0, explore
  generate(current + "1", n);   // choose 1, explore
}

const n = 2;
generate("", n);

00
01
10
11

🔁 How a single path runs

It helps to watch one path go all the way down and come back. Take the Java or C++ version with the shared builder, for n equal to 2.

• Start with an empty string "".
• Choose 0, now "0". Go deeper.
• Choose 0 again, now "00". Length is 2, so print 00. Come back.
• Un-choose, back to "0". Choose 1, now "01". Print 01. Come back.
• Un-choose twice, back to "". Choose 1, now "1". Go deeper.
• Choose 0, now "10". Print 10. Come back. Un-choose, choose 1, "11". Print 11.

That up and down walk is backtracking doing its job. Every time we come back up, the un-choose step cleans the spot for the next option.

⚖️ Backtracking vs plain brute force

People often mix these up, so let us put them side by side.

That skipping of whole branches has a name. It is called pruning. Pruning means cutting off a branch of the choice tree early because you already know nothing good can come from it. A maze walker who sees a dead end one step ahead does not keep walking into it. That saved walk is pruning.

⏱️ A word on cost

Backtracking explores a tree of choices, so its cost grows with how many leaves that tree has. For binary strings of length n there are two choices at each of n spots. That gives 2^n answers. So this kind of problem is naturally slow when n gets big. And there is no way around printing every answer if every answer is asked for.

⚠️ Common mistakes

A few traps catch almost everyone the first time:

• Forgetting to un-choose. With a shared list or builder, if you choose but never remove, the next branch starts dirty and your answers come out wrong.
• Un-choosing the wrong thing. Remove exactly what you added, nothing more. Adding one item and removing two leaves the state broken.
• No base case. Without the “if the answer is complete, record it and return” check, the recursion never stops and you crash.
• Saving a shared list by reference. If you store the same list object in your results, every entry points to the same thing and they all look the same. Save a copy.

🧩 What You’ve Learned

• ✅ Backtracking builds a solution step by step and undoes a step when it leads to a dead end.
• ✅ The pattern is always choose, explore, un-choose — add an option, recurse, then remove it.
• ✅ Every backtracking problem is a decision tree, and walking it to each leaf gives one complete answer.
• ✅ The un-choose step is what frees the state so the next option starts clean.
• ✅ Pruning drops bad branches early, which is what makes backtracking faster than plain brute force.

🚀 What’s Next?

• Generate Subsets
• Generate Permutations