Letter Combinations of a Phone Number — Cartesian Product Backtracking

Problem Statement#

LC 17 — Letter Combinations of a Phone Number. Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. The mapping of digits to letters follows the classic T9 phone keypad: 2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz. Note that 1 does not map to any letters.

Constraints: 0 <= digits.length <= 4. digits[i] is a digit in the range [2, 9].

Examples:

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

Why This Problem Matters#

This is the cleanest illustration of cartesian-product backtracking in any interview catalog. Amazon, Meta, Apple, and Uber ask it routinely as a 15-minute warm-up because solving it correctly proves the candidate has the choose / explore / unchoose pattern internalized. It also exposes whether the candidate handles the empty-input edge case gracefully — a small detail that is the most common reason for failed submissions.

Cartesian products power countless production systems. T9 keypad text input was the original reason this problem exists; modern equivalents include configuration enumeration (every combination of supported regions and languages), feature-flag matrices in A/B testing, and combinatorial test generation in QA. The mental model of "for each position, choose one option from a fixed set" is the same shape as enumerating all paths in a directed acyclic graph with fixed-out-degree nodes.

The problem also opens the door to two follow-up classics: an iterative BFS version that builds combinations level by level, and a generator/yield version that emits combinations lazily. Each illustrates a different trade-off, and being fluent in all three signals senior-level breadth.

The Core Insight#

Each digit independently contributes a SET of letters. For input "23", position 0 picks from {a, b, c} (digit 2) and position 1 picks from {d, e, f} (digit 3). The output is the cartesian product of the per-position letter sets.

Backtracking enumerates this product by recursing on the digit index. At index i, the for-loop iterates the letters mapped from digits[i], appends one to the path, recurses on i + 1, and pops on return. When i == len(digits), the path has one letter per digit — record it.

The output count is the product of the lengths of each letter set. Digits 2-6 and 8 each contribute 3 letters; digits 7 and 9 contribute 4. With len(digits) less-than-or-equal 4, the maximum output count is 4^4 = 256, comfortably small.

The empty-string base case is the single most common bug. When digits == "", the expected answer is [] (an empty list), NOT [""] (a list containing the empty string). The simplest fix is an early return at the top of the function. A subtle alternative is to inspect the result: if no recursion happens, no path is ever recorded, but if your base case is i == len(digits) and you start with i = 0, the empty input would record one empty string — so guard explicitly.

Visual Dry Run#

digits = "23". Decision tree (depth = 2).

bt(i=0, path="")
  letter 'a' -> bt(1, "a")
    letter 'd' -> bt(2, "ad") -> RECORD
    letter 'e' -> bt(2, "ae") -> RECORD
    letter 'f' -> bt(2, "af") -> RECORD
  letter 'b' -> bt(1, "b")
    letter 'd' -> RECORD "bd"
    letter 'e' -> RECORD "be"
    letter 'f' -> RECORD "bf"
  letter 'c' -> bt(1, "c")
    letter 'd' -> RECORD "cd"
    letter 'e' -> RECORD "ce"
    letter 'f' -> RECORD "cf"

Final: ["ad","ae","af","bd","be","bf","cd","ce","cf"]. Nine combinations equal 3 * 3 from the cartesian product.

Solution (Optimal)#

Python — recursive backtracking template#

def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []  # critical edge case: no digits -> no combinations
 
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi',
        '5': 'jkl', '6': 'mno', '7': 'pqrs',
        '8': 'tuv', '9': 'wxyz',
    }
    result: list[str] = []
    path: list[str] = []
 
    def bt(i: int) -> None:
        # Base: one letter per digit -> record the combination
        if i == len(digits):
            result.append(''.join(path))
            return
 
        for ch in mapping[digits[i]]:  # iterate letters for digit at position i
            path.append(ch)            # choose
            bt(i + 1)                  # explore next digit
            path.pop()                 # unchoose
 
    bt(0)
    return result
 
 
# Iterative BFS variant — builds combinations level by level
def letterCombinationsBFS(digits: str) -> list[str]:
    if not digits:
        return []
    mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
               '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    result = ['']
    for d in digits:
        # Expand each existing partial by the letters of the next digit
        result = [prev + ch for prev in result for ch in mapping[d]]
    return result

JavaScript#

function letterCombinations(digits) {
    if (!digits) return [];
 
    const mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi',
        '5': 'jkl', '6': 'mno', '7': 'pqrs',
        '8': 'tuv', '9': 'wxyz',
    };
    const result = [];
    const path = [];
 
    function bt(i) {
        if (i === digits.length) {
            result.push(path.join(''));
            return;
        }
        for (const ch of mapping[digits[i]]) {
            path.push(ch);            // choose
            bt(i + 1);                // explore
            path.pop();               // unchoose
        }
    }
    bt(0);
    return result;
}
 
// Iterative BFS variant
function letterCombinationsBFS(digits) {
    if (!digits) return [];
    const mapping = { '2':'abc','3':'def','4':'ghi','5':'jkl',
                      '6':'mno','7':'pqrs','8':'tuv','9':'wxyz' };
    let result = [''];
    for (const d of digits) {
        const next = [];
        for (const prev of result) {
            for (const ch of mapping[d]) {
                next.push(prev + ch);
            }
        }
        result = next;
    }
    return result;
}

Complexity#

The 4^N factor is the worst-case product when every digit maps to four letters (digits 7 and 9). The * N factor is the cost to copy the final string into the result list.

Common Mistakes#

1. Returning [""] instead of [] for empty input. Most failed submissions are this single edge case. Always early-return on empty digits.
2. Hardcoding the digit-to-letter map inside the recursion. Build the mapping as a constant at the top; recreating it inside each call wastes time and pollutes scope.
3. Forgetting that 1 and 0 have no mapping. The constraints rule out 0 and 1, but if your input is unsanitized you'll throw KeyError. Defensive code should assert digit in mapping.
4. Mutating result outside the base case. Append only when i == len(digits). Appending mid-recursion produces partial strings.
5. Using string concatenation in a tight inner loop in non-Python languages. Each + allocates a new string in JavaScript and Java; prefer a list or buffer for paths and join once at recording time.
6. Confusing iteration order. The cartesian product order depends on the order of letters in each digit's letter set — keep it as the standard T9 ordering for predictable output.

Interview Tips#

• Whiteboard the mapping first. Writing {2: 'abc', 3: 'def', ...} proves you remembered the keypad and gives you a reference for the rest of the code.
• Lead with the cartesian product framing. "This is a cartesian product over per-digit letter sets." Interviewers immediately know you understand the structure.
• Mention the BFS variant. Bringing it up unprompted shows you can choose between recursion and iteration based on context.
• Discuss space. The recursion uses O(N) stack; the BFS uses O(4^N) intermediate. Both produce O(4^N * N) output.
• Ask about lazy generation. "Should I yield combinations one at a time or materialize them?" — earns a knowing nod from senior interviewers.

Follow-up Questions#

• What if digit 1 had a custom mapping (or 0 mapped to space)? Extend the mapping dict — algorithm unchanged.
• Generate combinations sorted lexicographically. The recursive version is already lexicographic if letter sets are alphabetic; sort the per-digit sets if they aren't.
• Validate: does the dictionary contain any of these combinations as a real word (LC 211 / 79 trie)? Combine with a trie of real words to filter.
• Yield variant in Python or JavaScript generators. Replace result.append(...) with yield ... and the recursion turns into a coroutine.
• Phone-pad regex matching. Solve LC 17 paired with LC 10 / 44 to allow wildcards in digit positions.

Key Takeaways#

• Letter combinations of a phone number is a textbook cartesian-product enumeration solved by per-position backtracking.
• The recursion picks one letter from mapping[digits[i]] and recurses on i + 1; record the path when i == len(digits).
• The empty input must return [], not [""] — the single most common bug in interview submissions.
• The iterative BFS variant builds the result level by level and is sometimes preferred for its clarity and absence of recursion.
• Time and space are both O(4^N * N) where 4 is the maximum letters per digit (digits 7 and 9) and N is the input length.
• Mastery of this template extends to all fixed-out-degree DAG enumerations, feature flag matrices, and configuration grid searches.