Overview

Backtracking is a search technique that builds a solution step by step. It tries a choice, explores what follows, and returns to undo that choice when the path fails or has been fully explored. This choose–explore–undo pattern is widely used for puzzles, combinations, scheduling, and constraint problems.

Key concepts

• Choose one available option
• Check whether the partial solution is valid
• Explore valid choices recursively
• Undo the choice before trying the next option

What is Backtracking?

Think of exploring a maze. At every junction you choose a route. If that route reaches a dead end, you return to the most recent junction and try another. Backtracking applies this strategy to a tree of possible decisions.

Why do we need Backtracking?

Many problems contain a huge number of possible combinations. Backtracking avoids continuing down a branch as soon as it can prove that the current partial solution cannot become valid. This early rejection is called pruning.

How does Backtracking work?

• Start with an empty partial solution
• Choose one candidate
• Reject it immediately if it violates a constraint
• Explore it recursively if it remains valid
• Undo the choice after exploration
• Repeat for every candidate

A reusable Backtracking template

function backtrack(state, choices, results) {
  if (isComplete(state)) {
    results.push([...state]);
    return;
  }

  for (const choice of choices) {
    if (!isValid(state, choice)) continue;

    state.push(choice);       // Choose
    backtrack(state, choices, results); // Explore
    state.pop();              // Undo
  }
}

Real implementations define completion, available choices, and validity according to the problem.

Simple recursion example

This small example shows recursion moving forward and then unwinding in reverse order.

function backtrack(current) {
  if (current > 3) {
    return;
  }

  console.log(current);
  backtrack(current + 1);
  console.log("Backtracking from:", current);
}

backtrack(1);
// 1, 2, 3
// Backtracking from: 3, 2, 1

Example: generating Subsets

At each array position, choose whether to include the value. Copy a completed path before storing it because the same path array is changed during later exploration.

function subsets(numbers) {
  const results = [];
  const path = [];

  function explore(index) {
    if (index === numbers.length) {
      results.push([...path]);
      return;
    }

    path.push(numbers[index]); // Choose it
    explore(index + 1);
    path.pop();                // Undo

    explore(index + 1);       // Skip it
  }

  explore(0);
  return results;
}

console.log(subsets([1, 2]));
// [[1, 2], [1], [2], []]

Real-life example

Imagine entering a four-digit code one digit at a time. If a partial code violates a known rule, erase the latest digit and try another. Continue until a valid code is found or every possibility has been rejected.

Common Backtracking problems

• Sudoku Solver
• N-Queens
• Rat in a Maze
• Word Search
• Permutations
• Combinations
• Subsets
• Crossword Solver

Backtracking vs Brute Force

Backtracking is a structured form of exhaustive search. Pruning can make it much faster in practice, but it does not automatically change the worst-case exponential search space.

Backtracking vs Dynamic Programming

Time complexity

When all solutions must be returned, the algorithm needs enough time to produce them. Constraint checks, candidate ordering, and pruning reduce unnecessary exploration.

Pruning strategies

• Reject a choice as soon as it violates a constraint
• Stop when the remaining candidates cannot complete the target
• Try promising candidates first when only one solution is needed
• Track occupied rows, columns, or values with sets
• Avoid generating duplicate branches

Advantages of Backtracking

• Can find one or all valid solutions
• Avoids known-impossible branches
• Fits constraint-based problems naturally
• Combines cleanly with recursion
• Supports many classic interview problems

Limitations of Backtracking

• Worst-case running time is often exponential
• Deep recursion consumes call-stack memory
• Weak pruning can leave an enormous search
• Correct state restoration requires care
• Efficient validity checks can be difficult to design

Real-life applications

• Puzzle solving
• Route planning
• Timetable generation
• Resource scheduling
• Robot pathfinding
• Game solving
• Valid configuration generation
• Artificial Intelligence search

Tips for beginners

• Understand recursion first
• Say choose, explore, undo while tracing code
• Draw the decision tree
• Copy mutable paths when saving solutions
• Start with subsets and permutations
• Add pruning only after the basic search is correct

Key takeaways

• Backtracking explores a decision tree
• Its core pattern is choose → explore → undo
• Invalid partial solutions should be pruned early
• It commonly solves permutations, combinations, puzzles, and constraints
• Worst-case time is often exponential
• Correctly restoring state is essential
• Good pruning determines practical performance