LeetCode Letter Combinations of a Phone Number

Intermediate 8 min read

What you'll learn

✓How to set up the digit-to-letters map cleanly
✓A backtracking template indexed by digit position
✓How to handle empty input and invalid digits
✓The exact 3^n * 4^m complexity bound
✓How to talk about iterative vs recursive trade-offs

Prerequisites

•Comfort with [recursion](/blog/recursion-fundamentals)
•Familiarity with [hash maps](/blog/hashing-and-hash-maps)

Letter Combinations of a Phone Number (LeetCode 17, Medium) is the simplest backtracking problem on the list. It is also the cleanest place to practice index-based recursion before tackling harder enumeration problems.

The Problem

Given a string of digits 2-9, return all letter combinations that the digits could represent on a classic phone keypad.

Example:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

The mapping: 2 maps to abc, 3 to def, 4 to ghi, 5 to jkl, 6 to mno, 7 to pqrs, 8 to tuv, 9 to wxyz.

Brute Force

Nested loops only work if you know the digit count in advance. For a variable-length input, you must recurse anyway, so there is no real brute force; the natural solution is also the optimal solution.

Optimal Solution

Backtrack one digit at a time, appending a letter and recursing on the next digit.

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    }
    result = []
    path = []

    def backtrack(i):
        if i == len(digits):
            result.append(''.join(path))
            return
        for letter in mapping[digits[i]]:
            path.append(letter)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Linear recursion depth, branching factor 3 or 4 per digit.

Walk Through an Example

digits = "23".

i=0, digit 2, letters abc.
- Pick a, recurse on i=1.
  - i=1, digit 3, letters def.
    - Pick d: path [a,d]. Record "ad".
    - Pick e: record "ae".
    - Pick f: record "af".
- Pick b: record "bd", "be", "bf".
- Pick c: record "cd", "ce", "cf".

Nine combinations.

Edge Cases

Empty string: return [] per the problem statement.
Digit 1 or 0: the standard keypad has no letters; assume input excludes them as the LeetCode constraints say. If you must handle them, treat them as a no-op or error.
Long inputs: result size grows multiplicatively. 4 digits all mapping to 4-letter keys produce 256 results.
Repeated digits like “77”: still enumerates 16 strings.

Complexity Analysis

Time: O(3^n * 4^m) where n is the count of digits that map to 3 letters and m the count of digits that map to 4 letters. Each combination takes O(n+m) to build.
Space: O(n + m) recursion depth, plus output size.

This is also the output size, so it’s a tight bound.

How to Explain It in an Interview

Begin with the setup: “Each digit independently picks one of its 3 or 4 letters, so the total count is the product.” That motivates the index-based backtracking. Walk through one branch. Mention you could write an iterative BFS version that maintains a queue of partial strings; some interviewers prefer that, but recursion is cleaner. Call out the empty-string edge case explicitly.

LeetCode 39 Combination Sum
LeetCode 78 Subsets
LeetCode 46 Permutations
LeetCode 320 Generalized Abbreviation

Wrap up

Letter Combinations is the friendliest backtracking problem to practice clean recursion structure. Master it, and the harder enumeration problems become applications of the same template with extra constraints. Pair it with Big-O intuition to talk about why the output size dominates.