Letter Combinations of a Phone Number

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

Examples

The brute-force approach

Iteratively build combinations. Start with an empty list. For each digit, for each existing combination, append each letter that digit maps to.

result = [""]
for digit in digits:
    letters = phone[digit]
    result = [combo + letter
              for combo in result
              for letter in letters]

Not actually slow — this iterative BFS approach is O(4ⁿ × n) just like backtracking. But it builds many intermediate strings in memory. Backtracking builds one path at a time and discards it when done, using O(n) memory for the current path.

Spotting the pattern

This is a Backtracking problem. The key question to ask yourself:

At each position in the combination, what are the choices? When do you know a combination is complete?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.