Backtracking

Backtracking

Ever played a maze game where you hit a dead end and had to backtrack to try a different path? That's exactly what backtracking is in programming. It's a systematic way to explore all possible solutions by building a solution incrementally and undoing choices that lead to dead ends.

The pattern is simple: Choose, Explore, Unchoose. You make a choice, explore what happens next, and if it doesn't work out, you undo that choice and try something else. It's like trying different keys on a keyring - try one, if it doesn't fit, try the next one.

Backtracking is perfect for constraint satisfaction problems - puzzles, mazes, Sudoku, N-Queens, permutation generation. Basically any problem where you need to find all valid configurations or just one valid configuration among many possibilities.

The Backtracking Pattern

Here's the general approach: at each step, you have a set of choices. You try each choice, recursively explore what happens, and if you reach a valid solution, great! If not, you backtrack (undo your choice) and try the next option. This explores the entire solution space without having to enumerate everything upfront.

The key insight is that you're building a solution tree. Each node represents a partial solution, each edge represents a choice. Backtracking does a depth-first search of this tree, pruning branches that can't possibly lead to a solution. Smart and efficient.

function generatePermutations(arr, current = [], results = []) {
  if (current.length === arr.length) {
    results.push([...current]);
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    if (current.includes(arr[i])) continue;
    current.push(arr[i]);
    generatePermutations(arr, current, results);
    current.pop();
  }
  return results;
}

const nums = [1, 2, 3];
const perms = generatePermutations(nums);
console.log(perms);