juniorBacktracking

What is backtracking and how does it work internally?

Updated Feb 20, 2026

Short answer

Backtracking is an algorithmic technique that builds a solution step by step and abandons a path as soon as it determines that the path cannot lead to a valid solution. Internally, it usually uses recursion to explore choices, maintain the current state, undo the last choice, and try another possibility. It is essentially a depth-first search through a decision tree with pruning to avoid unnecessary work.

Deep explanation

Backtracking solves problems where we need to explore many possible combinations, arrangements, or paths while following certain constraints. Instead of trying every possibility blindly, it builds a solution incrementally and reverses decisions when they lead to invalid states.

The core idea is:

  1. Make a choice.
  2. Move forward with that choice.
  3. Check whether the current state is valid.
  4. If the state can still lead to a solution, continue exploring.
  5. If the state is invalid, undo the choice and try another option.

This "choose, explore, unchoose" pattern is the foundation of backtracking.

A typical backtracking algorithm looks like this:

Python
def backtrack(state):
    if is_solution(state):
        save_solution(state)
        return


    for choice in available_choices(state):
        make_choice(choice, state)


        if is_valid(state):
            backtrack(state)


        undo_choice(choice, state)

Backtracking usually relies on the program's call stack because it is commonly implemented with recursion.

For example, imagine generating all possible arrangements of [1, 2, 3].

The algorithm creates a decision tree:

TypeScript
[]
        /         |          \
      [1]       [2]          [3]
     /  \        ...          ...
 [1,2] [1,3]
   |
[1,2,3]

The algorithm explores one branch deeply before returning to explore another branch.

Internally:

  • A recursive call is made when the algorithm chooses a new option.
  • The current state is stored in memory, usually through local variables or a shared data structure.
  • When a branch fails or finishes, the function returns.
  • The algorithm removes the previous choice and restores the earlier state.

This restoration step is called backtracking.

Example of the recursion flow

Suppose we want to find subsets of {1, 2}.

The choices are:

TypeScript
Start: []


Choose 1:
    [1]


    Choose 2:
        [1,2]


    Undo 2:
        [1]


Undo 1:
    []


Choose 2:
    [2]


Undo 2:
    []

The algorithm repeatedly modifies the same state, explores possibilities, and restores the previous state.

Backtracking vs brute force

A brute-force approach checks every possible solution without using constraints early.

Backtracking improves this by pruning invalid paths.

For example, when solving a Sudoku puzzle:

  • Brute force might try every possible number arrangement.
  • Backtracking places a number, checks whether the board is still valid, and immediately stops exploring that branch if a rule is violated.

This pruning can reduce the search space significantly.

Common components of a backtracking solution

Most backtracking problems contain:

  • State: The current partial solution.
  • Example: numbers already placed in a combination.
  • Choices: Options available at the current step.
  • Example: possible numbers that can be added.
  • Constraint check: Determines whether the current state is allowed.
  • Example: whether a queen placement conflicts with another queen.
  • Base case: Determines when a complete solution is found.

Time and space complexity

Backtracking often has exponential time complexity because it may explore many possible states.

For example:

  • Generating all subsets of n elements takes:
TypeScript
O(2^n)

because every element has two choices: included or excluded.

  • Generating all permutations of n elements takes:
TypeScript
O(n!)

because there are n! possible orderings.

Space complexity depends on the recursion depth and stored results:

  • Recursive call stack: usually O(n).
  • Stored solutions may require much more space.

When to use backtracking

Backtracking is useful for problems involving:

  • Generating all possible combinations.
  • Finding arrangements or permutations.
  • Constraint satisfaction problems.
  • Searching through possible paths.
  • Puzzle solving.

Common examples include:

  • N-Queens problem.
  • Sudoku solver.
  • Word search.
  • Combination sum.
  • Maze solving.
  • Generating parentheses.

Real-world example

A practical example is assigning employees to project roles.

Suppose a company has three employees and three roles. Each employee has different skills, and we need to find a valid assignment where everyone gets a suitable role.

A backtracking approach tries an assignment, checks whether it is valid, and reverses it if it causes a conflict.

Example:

Python
def assign_roles(employees, roles, assignment):
    if len(assignment) == len(employees):
        return assignment


    employee = employees[len(assignment)]


    for role in roles:
        if role not in assignment.values() and employee.can_do(role):
            assignment[employee] = role


            result = assign_roles(employees, roles, assignment)


            if result:
                return result


            # Undo the choice
            del assignment[employee]


    return None

The algorithm:

  1. Assigns a role to the first employee.
  2. Recursively tries to assign roles to the remaining employees.
  3. If it reaches a conflict, it removes the assignment.
  4. It tries the next available role.

This allows the program to explore possible assignments without manually checking every complete arrangement.

Common mistakes

  • * Assuming backtracking always finds the fastest solution
  • it can still be expensive for large search spaces.
  • * Forgetting to undo changes after exploring a choice, which corrupts the state for later branches.
  • * Confusing backtracking with dynamic programming
  • backtracking explores choices, while dynamic programming usually stores overlapping results.
  • * Not adding pruning conditions, causing the algorithm to explore many impossible paths.
  • * Using recursion without considering stack depth limitations.
  • * Failing to define a clear base case, which can lead to infinite recursion.
  • * Modifying shared data structures incorrectly between recursive calls.
  • * Thinking backtracking only applies to puzzles
  • it is a general search technique used in many optimization and constraint problems.

Follow-up questions

  • How is backtracking different from depth-first search?
  • Why does backtracking use recursion so often?
  • What is pruning in backtracking?
  • How can you optimize a backtracking algorithm?
  • What is the difference between backtracking and dynamic programming?
  • What are some common interview problems solved using backtracking?

More Backtracking interview questions

View all →