Introduction

This problem is a classic backtracking problem: each digit maps to a small set of letters, and the full result is every possible way to choose one letter per digit. The algorithm is simple once you stop thinking in terms of hard-coded cases and instead treat the input as a sequence of branching choices.

The core challenge is not the mapping itself. It is building combinations incrementally while keeping the recursion state clean and handling edge cases such as empty input or unsupported digits.

Model the Keypad First

The standard phone keypad mapping is:

• '2 to abc'
• '3 to def'
• '4 to ghi'
• '5 to jkl'
• '6 to mno'
• '7 to pqrs'
• '8 to tuv'
• '9 to wxyz'

Digits 0 and 1 usually have no letter mapping in interview versions of the problem. Decide up front whether your function should reject them or ignore them.

Backtracking Solution

A clean way to solve the problem is depth-first search. At each position, choose one letter for the current digit, append it to the partial path, recurse to the next digit, and then remove the letter before trying the next branch.

1from typing import List
2
3
4def letter_combinations(digits: str) -> List[str]:
5    if not digits:
6        return []
7
8    mapping = {
9        "2": "abc",
10        "3": "def",
11        "4": "ghi",
12        "5": "jkl",
13        "6": "mno",
14        "7": "pqrs",
15        "8": "tuv",
16        "9": "wxyz",
17    }
18
19    for digit in digits:
20        if digit not in mapping:
21            raise ValueError(f"unsupported digit: {digit}")
22
23    result: List[str] = []
24    path: List[str] = []
25
26    def dfs(index: int) -> None:
27        if index == len(digits):
28            result.append("".join(path))
29            return
30
31        for ch in mapping[digits[index]]:
32            path.append(ch)
33            dfs(index + 1)
34            path.pop()
35
36    dfs(0)
37    return result
38
39
40print(letter_combinations("23"))

For input 23, the result is:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Why Backtracking Fits So Well

The search tree mirrors the problem exactly. If the input has n digits, the recursion depth is n. Each level chooses one letter from the current digit's mapping.

That gives you a few nice properties:

• every completed path has the correct length
• no invalid letters are generated
• the algorithm does not need post-filtering
• memory stays proportional to the current path plus the output list

The time complexity is exponential, but that is unavoidable because the number of valid outputs is exponential too.

Iterative Alternative

If you prefer iteration, you can build combinations left to right by expanding a working list.

1def letter_combinations_iterative(digits: str):
2    if not digits:
3        return []
4
5    mapping = {
6        "2": "abc",
7        "3": "def",
8        "4": "ghi",
9        "5": "jkl",
10        "6": "mno",
11        "7": "pqrs",
12        "8": "tuv",
13        "9": "wxyz",
14    }
15
16    combinations = [""]
17    for digit in digits:
18        if digit not in mapping:
19            raise ValueError(f"unsupported digit: {digit}")
20        combinations = [prefix + ch for prefix in combinations for ch in mapping[digit]]
21
22    return combinations
23
24
25print(letter_combinations_iterative("79"))

This is still the same combinatorial expansion, just written without recursion.

Printing Versus Returning

If the only requirement is printing, you can print each combination inside the base case instead of storing it in a list. That avoids holding the full output in memory.

1def print_combinations(digits: str) -> None:
2    mapping = {
3        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
4        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
5    }
6    path = []
7
8    def dfs(index: int) -> None:
9        if index == len(digits):
10            print("".join(path))
11            return
12        for ch in mapping[digits[index]]:
13            path.append(ch)
14            dfs(index + 1)
15            path.pop()
16
17    if digits:
18        dfs(0)

That version is useful if the output is large and you only need side effects such as printing or streaming.

Common Pitfalls

The first mistake is forgetting to handle empty input, which should usually return an empty list. Another is ignoring unsupported digits such as 0 and 1 and then getting a lookup error mid-recursion. Developers also sometimes build strings with repeated concatenation at every step; that works, but a mutable path list is cleaner and avoids extra temporary objects. Finally, some people underestimate the output size. A seven-digit input can already generate thousands of combinations.

Summary

• Build a digit-to-letters map first.
• Use backtracking to choose one letter per digit.
• The algorithm is exponential because the output itself is exponential.
• Validate how your function should handle 0, 1, and empty input.
• If you only need printing, emit combinations in the base case instead of storing them all.