Letter Combinations of a Phone Number

Backtracking becomes much easier when you can name what one recursive call means. Here, each call assigns one phone-keypad digit, and each complete path becomes one output string.

Read the output contract first

The input is a string of digits from 2 through 9. Each digit contributes exactly one letter:

Digit	Letters
2	abc
3	def
4	ghi
5	jkl
6	mno
7	pqrs
8	tuv
9	wxyz

For every input digit, choose one letter from its mapping. Preserve the digit order.

For example, "23" means:

• choose one letter from "abc"
• then choose one letter from "def"

That produces nine results:

ad ae af bd be bf cd ce cf

Every result has the same length as the input. The output order does not matter, so the implementation can explore choices in any consistent order.

The standard constraints give an input length from 1 through 4, with every digit in the range 2 through 9. In Python, it is still useful to handle "" defensively by returning []. Digit 1 has no mapping under this problem contract, so it does not need a branch in the solution.

The important question is not “where is the backtracking template?” It is:

What does one recursive level decide?

Here, one recursive level decides the letter for one input position.

Recognize the Cartesian-product tree

This is a Cartesian product problem: choose one item from each of several sets, while preserving the order of those sets.

For "23":

digit 2: a, b, c
digit 3: d, e, f

The first tree level has three choices. From each of those choices, the second level has three more choices.

                 ""
          /       |       \
         a        b        c
       / | \    / | \    / | \
     ad ae af bd be bf cd ce cf

Each root-to-leaf path is one complete answer.

This classification gives you the algorithm almost immediately:

1. Start with an empty path.
2. Choose one letter for the current digit.
3. Recurse to the next digit.
4. Undo the choice.
5. Try the next letter.

There is no meaningful pruning here. Every partial path can still become a valid result because each digit must receive exactly one letter, and no target or validity condition can disqualify a prefix.

That makes this different from other backtracking problems:

• Combination Sum has a remaining-target condition and may reuse candidates.
• Generate Parentheses tracks whether a parenthesis choice preserves balance.
• Problems with duplicate candidates may skip branches to avoid repeated output.

This problem has none of those constraints. We are enumerating every branch of a fixed-depth tree.

Trying to invent pruning would only hide the real structure. The output itself is the work.

Define the state and transition

Let backtrack(i) mean:

The first i digits have already been assigned, and path contains exactly the selected letters for those digits.

That gives us a precise state:

• i: the next digit position to process
• path: the partial combination built so far
• results: all complete combinations found so far

At position i, look up the letters for digits[i]. For each available letter:

1. Append it to path.
2. Recurse with i + 1.
3. Pop it from path.

The stopping condition is i == n, where n is the input length. At that point, every digit has been assigned, so path is complete and can be joined into a string.

The invariant to keep in your head while debugging is:

Whenever backtrack(i) starts, len(path) == i, and path represents valid choices for the first i digits.

That invariant explains both the recursive call and the pop().

• The append makes the path one character longer.
• The recursive call advances to the next digit.
• The pop restores the exact state needed to try the next sibling branch.

The mutable list is deliberate. We reuse one path object while exploring the tree instead of constructing a new partial string for every recursive call.

Trace one digit and two digits

Start with "2".

The initial state is:

i = 0
path = []

Digit 2 maps to "abc".

Choice	Path before recursion	Recursive state	Result
a	["a"]	i = 1	"a"
undo	[]	back at i = 0	—
b	["b"]	i = 1	"b"
undo	[]	back at i = 0	—
c	["c"]	i = 1	"c"

When i reaches 1, it equals n, so the current path is complete.

Now trace "23" through the first branch:

path = []
choose a
path = [a]

choose d
path = [a, d]
i == n
record "ad"

pop d
path = [a]

choose e
path = [a, e]
i == n
record "ae"

pop e
path = [a]

choose f
path = [a, f]
i == n
record "af"

pop f
path = [a]

pop a
path = []

The algorithm then repeats the same process for b and c.

The pop operations are the hinges of the whole procedure. Without them, the next branch inherits letters from the previous branch. For example, after producing "ad", failing to remove d would leave stale state in path. The next attempt would begin from ["a", "d"] instead of ["a"].

Read the state. Trace the mutation. The bug becomes visible.

Prove the enumeration is correct

A solution that matches "23" is plausible. The invariant explains why it works for every valid input.

Base case

When i == n, the algorithm has assigned one letter to every digit.

Because each selected letter came from the mapping of its corresponding digit:

• the path is valid,
• the path has length n,
• joining the path produces one complete combination.

The algorithm records the result only at this point, so it never records an incomplete prefix.

Recursive step

Assume backtrack(i + 1) correctly generates every valid suffix for the digits after position i.

At position i, the loop tries every letter mapped from digits[i]. For each one:

1. That letter becomes the choice for the current position.
2. The recursive call generates every valid way to complete the remaining positions.
3. The choice is removed before the next letter is tried.

Therefore, the current call generates every valid combination beginning with the current path, and it does not miss any available choice.

No duplicates

Each result corresponds to one sequence of choices:

• one choice for digit 0,
• one choice for digit 1,
• and so on.

The loop visits each mapping entry once at each position. Since the input position and selected letter determine the branch, each choice sequence is visited once.

The pop() does not remove an answer from results. It only restores the temporary construction state so the next branch can be explored independently.

Implement the Python solution

Here is the complete recursive solution:

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []

    digit_to_letters = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

    results = []
    path = []
    n = len(digits)

    def backtrack(i: int) -> None:
        if i == n:
            results.append("".join(path))
            return

        for letter in digit_to_letters[digits[i]]:
            path.append(letter)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return results

Each variable has a specific obligation:

• digit_to_letters defines the available choices for each input position.
• results stores complete outputs.
• path stores the current root-to-node path.
• i identifies the next unassigned digit.
• n defines when the path is complete.

The order inside the loop matters:

path.append(letter)
backtrack(i + 1)
path.pop()

Appending before recursion assigns the current position. Recursing explores all later positions. Popping afterward restores the parent state.

A common mistake is to append a character and immediately create a new string in a way that obscures which state belongs to which call. That can work, but the mutable path makes the decision tree explicit. For an interview, visible state is usually more valuable than compressed code.

An iterative layer-by-layer version is also valid. It starts with [""], then extends every partial string using the next digit’s letters. That is still Cartesian-product generation. I prefer the recursive version here because the teaching target is the decision tree: choose, recurse, undo.

Analyze the output cost

Let b_i be the number of letters mapped from the digit at position i.

The number of returned combinations is:

[ T = \prod_{i=0}^{n-1} b_i ]

For example:

• "23" produces 3 × 3 = 9 results.
• "79" produces 4 × 4 = 16 results.
• A length-n input can produce at most 4^n results because digits 7 and 9 have four letters each.

Each output string has length n, so creating and storing all returned strings costs:

[ O(n \cdot T) ]

Using the maximum branching factor, this is commonly written as:

[ O(n \cdot 4^n) ]

The n factor matters. Producing a result such as "ad" requires joining two characters; producing a result of length n requires handling n characters. This is an output-sensitive problem: the algorithm cannot avoid spending work proportional to the data it is required to return.

Space has two parts:

• Auxiliary space: O(n) for the path and recursion stack.
• Output storage: O(n · T) for all returned strings.

When someone reports only O(n) space, they are excluding the output list. That can be a useful convention, but say so explicitly. The returned combinations still occupy memory.

Test boundaries and failure modes

Do not test only the canonical "23" example. Check the structure that the code depends on.

Empty input

letter_combinations("")
# []

The problem constraints may require at least one digit, but the defensive guard makes the function behavior clear.

One digit

letter_combinations("2")
# ["a", "b", "c"]

This verifies that the base case is reached immediately after one choice.

Two digits

letter_combinations("23")
# nine strings, each of length 2

This checks branching across multiple levels.

Four-letter mapping

letter_combinations("7")
# ["p", "q", "r", "s"]

This catches an incomplete mapping that assumes every digit has exactly three letters.

Mixed maximum branching

letter_combinations("7979")

The expected count is:

[ 4 \times 4 \times 4 \times 4 = 256 ]

For any test case, validate properties rather than relying on one output order:

• the number of results equals the product of mapping sizes,
• every result has length len(digits),
• character j belongs to the mapping for digits[j],
• no result contains a character from the wrong position,
• no result is duplicated,
• the final output does not change when the temporary path is reused.

That last check targets mutable-state corruption. If the code stores path itself instead of storing "".join(path), later mutations can make every stored entry reflect the same final state. Record an immutable string at the base case.

The reusable recognition rule

When every input position offers a small independent set of choices, and the task asks for every ordered selection:

1. Create one recursive level per input position.
2. Store the current partial assignment.
3. Try every choice for the current position.
4. Stop when every position is assigned.
5. Undo the last choice before trying the next sibling.

That is the core of this Letter Combinations of a Phone Number solution. The real cost is the number of outputs, not the elegance of the recursion.

Before writing the loop in your next interview, write the invariant:

backtrack(i) has assigned exactly the first i positions.

Once that sentence is true, the code has somewhere solid to stand.