Why Backtracking and What Greedy Cannot Solve in DSA Typescript - The Real Reason

The Big Idea

What if the fastest choice leads you nowhere? Discover why trying all paths matters!

The Scenario

Imagine you are trying to find the best path through a maze with many choices at each step. You try to pick the easiest-looking path first, hoping it leads to the exit quickly.

The Problem

Choosing the easiest path first (greedy way) can lead you into dead ends or miss the best overall path. You might waste time going back and forth, or never find the exit because you didn't explore other options.

The Solution

Backtracking helps by trying each possible path step-by-step. If a path fails, it goes back and tries another. This way, it explores all options systematically until it finds the best or all solutions.

Before vs After

✗ Before

function greedyMazeSolver(maze) {
  let path = [];
  // Always pick the next step that looks best
  // May miss the correct path
  return path;
}

✓ After

function backtrackingMazeSolver(maze, position, path) {
  if (position === exit) return path;
  for (const step of getPossibleSteps(maze, position)) {
    if (isSafe(step)) {
      path.push(step);
      if (backtrackingMazeSolver(maze, step, path)) return path;
      path.pop();
    }
  }
  return false;
}

What It Enables

Backtracking enables finding all possible solutions or the best solution when simple greedy choices fail.

Real Life Example

Solving puzzles like Sudoku or the N-Queens problem where placing one piece affects future choices and greedy guesses often fail.

Key Takeaways

Greedy methods pick the best immediate choice but can miss the overall best solution.

Backtracking tries all options by exploring and undoing steps when needed.

Backtracking is essential for problems with complex constraints and multiple solutions.