Backtracking

Backtracking is a classic algorithmic strategy that feels a bit like trying on different keys until you find the one that fits, but with a methodical twist. If you’ve ever played Sudoku, solved a maze, or explored multiple choices in a game, you’ve already used backtracking.

What Is Backtracking?

Think of backtracking as a smart “trial and error” approach. Instead of blindly checking every possible combination, you build solutions one step at a time. If you hit a dead end, you back up (or "backtrack") to try a different path. It’s like retracing your steps in a maze whenever you hit a wall, ensuring you eventually cover all possible routes, but never getting lost.

How to Identify a Backtracking Problem

Let’s talk about how you can recognize when a problem is a good fit for backtracking.

Ask yourself these questions:

• Does the problem ask you to find all solutions, or any valid solution, from a huge number of possibilities?
• Are you making a sequence of choices, where each choice leads to further choices?
• Can you “undo” or back up a choice if it doesn’t lead to a solution?
• Is brute-forcing every combination possible, but slow or repetitive?

Common Signs:

• You’re working with combinations, permutations, or subsets (for example, generating all possible arrangements of something).
• You need to solve puzzles, such as Sudoku, N-Queens, or crossword filling.
• You’re searching through a maze or a tree of possibilities.

If the answer to any of these is yes, there’s a good chance backtracking is the way to solve the problem.

How to Set Up a Backtracking Solution

Once you recognize a backtracking problem, the setup follows a simple pattern. Think of it like setting up a board game: you have a starting point, a set of possible moves, and a way to check if you’ve won i.e met the condition.

Here’s a step-by-step approach:

1. Define the Choices:
   
   Figure out what decisions you make at each step. In our keypad example, the choice is which letter to pick for the current digit.

2. Track the Path:
   
   Keep track of the current sequence of choices (this could be a list, string, or array).

3. Set the Goal:
   
   Decide when a solution is “complete.” For the keypad problem, a complete path is when you’ve picked a letter for every digit.

4. Implement the Backtracking Function:

   • At each step, loop through all available choices.
   • Add the choice to your path.
   • Recursively try the next step.
   • If you reach the goal, record the solution.
   • Remove the last choice (backtrack) and try the next possibility.

Visualizing It:

Imagine you’re navigating a tree, where each branch is a choice. You explore a branch, and if you reach a leaf (end of the path) that isn’t a solution, you move back to the previous fork and try a different branch.

Template Code Structure:

def backtrack(choices, path):
    if is_goal(path):
        save_solution(path)
        return
    for choice in choices:
        make_choice(path, choice)
        backtrack(next_choices, path)
        undo_choice(path)

This pattern pops up in all sorts of classic backtracking problems.

A Step-By-Step Walkthrough: Letter Combinations of a Phone Number

Let’s see backtracking in action with a real coding example: generating all possible letter combinations for a string of digits, just like texting on an old-school phone keypad.

Problem Recap

Given a string of numbers like "23", return all possible letter combinations those numbers could represent on a phone keypad.

Code Example

Here’s a Python implementation using backtracking:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []

        keypad = {
            '2': ['a','b','c'],
            '3': ['d','e','f'],
            '4': ['g','h','i'],
            '5': ['j','k','l'],
            '6': ['m','n','o'],
            '7': ['p','q','r','s'],
            '8': ['t','u','v'],
            '9': ['w','x','y','z']
        }

        def backtrack(index, path):
            if len(path) == len(digits):
                combinations.append("".join(path))
                return
            possible = keypad[digits[index]]
            for letter in possible:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()

        combinations = []
        backtrack(0, [])
        return combinations

How It Works: Step by Step

Let’s break this down as if you’re walking through a decision tree, one branch at a time.

1. Set Up the Problem:
   
   We check if digits is empty. If so, return an empty list. No digits means no combinations.

2. Keypad Mapping:
   
   We map each digit to its possible letters, like you see on a phone keypad.

3. Backtracking Function:

   • Goal: Build all combinations by picking one letter for each digit, moving from left to right.
   • Parameters:
     • index: Which digit we’re working on.
     • path: The current combination we’re building (as a list of characters).

4. The Recursion:

   • If path has as many letters as the input digits, we’ve built a full combination and add it to combinations.
   • Otherwise, look up the current digit in the keypad mapping and try each letter:
     • Add the letter to path.
     • Recursively call backtrack to work on the next digit.
     • After the recursive call, pop the last letter. This is the backtrack step, undoing our last choice so we can try another.

A Quick Example

If the input is "23", the algorithm explores:

• First digit 2: try a, b, c
• For each letter from 2, try all possibilities for digit 3: d, e, f

So it generates combinations like ad, ae, af, bd, be, bf, and so on.

Why Pop from Path?

That little line path.pop() is crucial. After trying a letter, we remove it to return path to its previous state, ready to try the next possibility. Think of it like removing a chess piece before trying a different move.

Backtracking is about exploring choices, retracing your steps, and efficiently finding all solutions. It’s perfect for situations where you need to try every combination, but want to avoid unnecessary work by skipping impossible paths early.

Whether you’re generating letter combos, solving puzzles, or navigating a maze, understanding backtracking will give you a powerful tool for tackling all kinds of problems without brute force.