Letter Combinations of a Phone Number

Letter Combinations of a Phone Number is the classic introduction to backtracking. It teaches how to enumerate every option across a sequence of independent choices by building a decision tree and walking it to every leaf.

The slow way first

You could write nested loops: one loop per digit. For "23" that is two loops; for "234" it is three. But the number of digits is not fixed, so you cannot hard-code the loop nesting. Hand-rolling a variable number of nested loops is awkward and error-prone.

The question to ask: how do I make one choice, commit to it, then make the next choice — for as many digits as there are? That is exactly what recursion does naturally: each level of the recursion picks a letter for one digit.

The idea: build a tree, walk every path

Treat it as a decision tree. The root is the empty string. For the first digit, branch once per letter. From each of those nodes, branch again for the second digit, and so on. Every root-to-leaf path spells one combination.

Backtracking is how we walk it: append a letter (choose), recurse to the next digit, and when that branch is fully explored, drop back up and try the next letter. We never build dead strings — every path runs to a complete combination.

Walk through it

Step through the animation. We start at the root with an empty prefix. We choose a, descend to digit 3, and emit ad, ae, af. Then we backtrack to the root, choose b, and emit bd, be, bf. Finally c gives cd, ce, cf. Nine leaves, nine combinations.

Pseudocode

keypad = map each digit -> its letters
result = empty list
function backtrack(i, path):
    if i == number of digits:        # placed a letter for every digit
        add path to result           # one full combination
        return
    for each letter of keypad[digit i]:
        backtrack(i + 1, path + letter)   # choose, then recurse
 
if digits is non-empty:
    backtrack(0, "")
return result

The Python solution

def letter_combinations(digits):
    keypad = {"2": "abc", "3": "def", "4": "ghi",
              "5": "jkl", "6": "mno", "7": "pqrs",
              "8": "tuv", "9": "wxyz"}
    result = []
    def backtrack(i, path):
        if i == len(digits):
            result.append(path)
            return
        for letter in keypad[digits[i]]:
            backtrack(i + 1, path + letter)
    if digits:
        backtrack(0, "")
    return result

• keypad maps each digit character to its string of letters.
• backtrack(i, path) means: we have already chosen letters for digits 0..i-1, and path is the prefix built so far.
• Lines 7-8 are the base case: when i equals the number of digits, path is a complete combination, so we record it and return.
• Line 10 loops over every letter the current digit digits[i] can be.
• Line 11 is the choose + recurse step: we extend the prefix with one letter and dive to the next digit. When that call returns, the loop moves to the next letter — that is the backtrack.
• The if digits: guard returns an empty list for empty input instead of [""].

Complexity

With n digits and up to 4 letters each, there are up to 4^n leaves, and each takes O(n) to assemble — so O(n · 4^n) total. The extra space beyond the output is O(n) for the recursion depth and the current path. This explosion is inherent: we are required to produce every combination.

When this pattern shows up

Practice