Letter Combinations of a Phone Number

Given a digit string (2-9), return all possible letter combinations based on telephone keypad mapping. Order does not matter.

Why this is worth learning

This is a Cartesian product, not a membership search. Each digit fixes a position and supplies its allowed letters; every full tuple is an answer, so output size is an unavoidable cost.

Before coding: one-minute experiment

How many results come from digits 79, and how many bytes are written just to store those result strings?

Function signature

func LetterCombinations(digits string) []string

Inputs / outputs

• digits: string of digits 2-9.
• Return: all possible letter combinations.

Example

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

Constraints

• 0 <= len(digits) <= 4

Core idea (near-solution)

Start with one empty partial string and extend every partial string with each letter of the next digit. For "27", three first-position choices each need four second-position choices: all 12 outputs are required. No search method can skip writing them. The useful saving is to share one prefix buffer while visiting the choices, copying only completed strings; the digit index already determines the next decision.

This is a Cartesian product over digit-to-letter mappings. Use backtracking to build one character at a time.

Invariant: the current path has length i and matches the first i digits.

Algorithm (step-by-step)

1. If digits is empty, return empty slice.
2. Map digits to letter strings ("2" -> "abc", etc.).
3. DFS with index i and buffer path:
   • If i == len(digits), record the string.
   • For each letter in mapping[digits[i]], append, recurse at i+1, then restore the previous path length before the next letter.
4. Return the results.

Correctness sketch

At recursion depth i, the path has exactly i letters, each chosen from the corresponding digit mapping. Extending by every allowed letter preserves this invariant. At depth n the path is a legal combination and is copied into an independent string. Every possible combination has one unique sequence of choices, so it is reached once and no invalid string is emitted. Popping after each recursive call restores the prefix for the next sibling. The explicitly empty input returns an empty result rather than the mathematical Cartesian-product identity containing one empty string.

Trace (hand walkthrough)

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

Walk:
- digits "2" -> [a,b,c]
- extend with "3" (d,e,f) -> ad, ae, af, bd, be, bf, cd, ce, cf

Pitfalls to avoid

• Returning []string{""} for empty input (should be empty).
• Using rune-based iteration incorrectly (letters are ASCII here).

Debugging lens

Test 7 and 9, whose mappings have four letters. Do not append a mutable path buffer by alias. Preserve the empty-input convention instead of unconditionally emitting an empty string.

Complexity

Let P be the product of the mapping sizes, with n digits. Time O(n P), including copying each length-n output; P lies between 3^n and 4^n. Auxiliary recursion/path space O(n), excluding O(n P) output storage.

Implementation notes (Go)

• Use a []byte buffer for the current path and convert to string on output.

Reconstruction checkpoint

How many results come from digits 79, and how many bytes are written just to store those result strings?

Return to Backtracking · Module quiz