Backtracking Theory

Backtracking

Welcome to Backtracking, a powerful algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point in time.

---

1. The Core Idea: Explore, Choose, and Backtrack

Think of backtracking as exploring a maze. You explore one path, and if you hit a dead end, you "backtrack" to the last junction and try a different path. This is exactly how backtracking algorithms work. They explore the "solution space" of a problem, which is the set of all possible solutions.

At each step, the algorithm makes a choice and then recursively tries to find a solution. If the choice leads to a dead end, it undoes the choice (backtracks) and tries another option.

---

2. A General Template for Backtracking

Most backtracking problems can be solved using a similar recursive template:

function backtrack(candidate, inputData) {
  if (isSolution(candidate, inputData)) {
    // Found a solution, process it
    return;
  }

  // Iterate through all possible choices
  for (const choice of generateChoices(candidate, inputData)) {
    // 1. Make a choice
    addChoiceToCandidate(choice, candidate);

    // 2. Recurse
    backtrack(candidate, inputData);

    // 3. Backtrack (undo the choice)
    removeChoiceFromCandidate(choice, candidate);
  }
}

---

3. Classic Problems

3.1. Permutations

Given a set of distinct numbers, find all possible permutations.

function findPermutations(nums) {
  const result = [];
  const currentPermutation = [];
  const used = Array(nums.length).fill(false);

  function generate() {
    if (currentPermutation.length === nums.length) {
      result.push([...currentPermutation]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      used[i] = true;
      currentPermutation.push(nums[i]);
      generate();
      currentPermutation.pop();
      used[i] = false;
    }
  }

  generate();
  return result;
}

3.2. Subsets

Given a set of distinct integers, return all possible subsets (the power set).

function findSubsets(nums) {
  const result = [];
  const currentSubset = [];

  function generate(index) {
    result.push([...currentSubset]);

    for (let i = index; i < nums.length; i++) {
      currentSubset.push(nums[i]);
      generate(i + 1);
      currentSubset.pop();
    }
  }

  generate(0);
  return result;
}

3.3. N-Queens and Sudoku Solvers

Backtracking is also perfectly suited for solving puzzles with constraints, like the N-Queens problem (placing N queens on an N×N chessboard so that no two queens threaten each other) and Sudoku solvers.

---

4. Pruning: The Key to Efficiency

A naive backtracking approach can be very slow. The key to making backtracking algorithms efficient is pruning. This means we stop exploring a path as soon as we can determine that it cannot possibly lead to a valid solution. The earlier you can prune a branch of the search space, the faster your algorithm will be.

---

Key Takeaway: Backtracking is a systematic way to explore all possible solutions to a problem. It shines in scenarios involving permutations, combinations, and constraint satisfaction problems. The core strategy is to choose, recurse, and backtrack, with pruning being the key to performance.