Letter Combinations of a Phone Number: Backtracking

May 4, 20269 min read

leetcodeproblemmediumbacktracking

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent on a phone keypad. Return the answer in any order.

This is LeetCode 17: Letter Combinations of a Phone Number, and it is a classic backtracking problem that shows up constantly in interviews. If you have already worked through Permutations and Subsets, you will recognize the same choose-explore-unchoose skeleton here. The twist is that the candidates at each level come from a digit-to-letter mapping instead of from the input array itself.

Phone keypad mapping. Digits 2-9 each map to 3 or 4 letters. For input "23", digit 2 maps to [a, b, c] and digit 3 maps to [d, e, f].

Why this problem matters

Letter combinations of a phone number teaches you how to apply the backtracking template when the branching factor changes at each level. In Subsets, every level has exactly 2 branches (include or skip). In Permutations, level k has n-k branches. Here, each level has 3 or 4 branches depending on which digit you are processing. The algorithm does not care. The choose-explore-unchoose template handles all of these cases without modification.

This problem also forces you to separate the "mapping" concern from the "search" concern. You need a dictionary that converts digits to letters, and then a backtracking function that walks through the digits one at a time, choosing a letter for each. Keeping those two things clean and separate is a skill that transfers to harder problems like Sudoku and word ladder.

Understanding backtracking combinations also helps you reason about the output size. If the input is "234", the digits map to 3, 3, and 3 letters respectively, so the output has 3 * 3 * 3 = 27 combinations. The number of results is the product of the letter counts for each digit. That is the total work the algorithm must do, and there is no shortcut.

The key insight

Think of building each combination one character at a time. You process the digits left to right. For the first digit, you have 3 or 4 letter choices. For the second digit, again 3 or 4 choices. And so on. Each path through this decision tree produces one complete combination.

The algorithm is straightforward:

Map each digit to its letters (2 -> "abc", 3 -> "def", etc.).
Start with an empty string and the first digit.
For the current digit, loop through its mapped letters. For each letter, append it to the current combination (choose), recurse to the next digit (explore), then remove the letter (unchoose).
When you have processed all digits, the current string is a complete combination. Record it.

That is it. No visited set, no sorting, no pruning. Pure backtracking.

Backtracking tree for digits = "23". At each level we pick one letter for the current digit. The 9 leaves are all 3 x 3 combinations.

The backtracking solution

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

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

    def backtrack(i, current):
        if i == len(digits):
            result.append(current)
            return

        for letter in phone[digits[i]]:
            backtrack(i + 1, current + letter)  # choose + explore

    backtrack(0, "")
    return result

Let's walk through this.

The phone dictionary maps each digit to its corresponding letters. This is the mapping layer, kept completely separate from the search logic.

The backtrack function takes two arguments: i (which digit we are processing) and current (the combination built so far). When i equals the length of the input, we have assigned a letter to every digit, so we record current and return.

The for loop iterates over every letter mapped to digits[i]. For each letter, we recurse with i + 1 and current + letter. Since Python strings are immutable, current + letter creates a new string. There is no explicit "unchoose" step because the original current is never modified. The next iteration of the loop automatically uses the unmodified current with the next letter.

In Python, string concatenation handles the unchoose step implicitly because strings are immutable. If you use a mutable list instead (appending and popping), you would need an explicit unchoose step just like in Permutations.

Practice backtracking letter combinations with spaced repetition

Visual walkthrough

Let's trace through the algorithm with digits = "23". Digit 2 maps to [a, b, c] and digit 3 maps to [d, e, f]. Watch how each level processes one digit and how the branching creates all 9 combinations.

Start: backtrack(0, ""). We are at digit index 0, which is "2". Letters are "abc".

Branch "a": We call backtrack(1, "a"). Now at digit index 1, which is "3". Letters are "def".

backtrack(2, "ad") -> record "ad"
backtrack(2, "ae") -> record "ae"
backtrack(2, "af") -> record "af"

Branch "b": Back to backtrack(0, ""), next iteration. We call backtrack(1, "b").

backtrack(2, "bd") -> record "bd"
backtrack(2, "be") -> record "be"
backtrack(2, "bf") -> record "bf"

Branch "c": Same pattern. We call backtrack(1, "c").

backtrack(2, "cd") -> record "cd"
backtrack(2, "ce") -> record "ce"
backtrack(2, "cf") -> record "cf"

Result: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. That is 3 * 3 = 9 combinations, exactly what we expected.

The mutable-list version

If you prefer the explicit choose-explore-unchoose pattern (or your interviewer asks to see it), here is the same algorithm using a list:

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

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

    def backtrack(i, current):
        if i == len(digits):
            result.append("".join(current))
            return

        for letter in phone[digits[i]]:
            current.append(letter)       # choose
            backtrack(i + 1, current)    # explore
            current.pop()                # unchoose

    backtrack(0, [])
    return result

This version makes the three backtracking steps visible. current.append(letter) is choose. The recursive call is explore. current.pop() is unchoose. The join at the base case converts the list to a string.

Both versions produce identical output with the same time complexity. The string version is slightly more Pythonic. The list version makes the backtracking pattern more explicit, which can be helpful during an interview explanation.

The string version creates a new string at each recursive call, so it uses O(n) extra space per call frame (where n is the number of digits). The list version mutates in place and only uses O(n) total for the current list. In practice, both are fine for this problem since n is at most 4.

Drill the choose-explore-unchoose pattern

Complexity analysis

Aspect	Complexity
Time	O(n * 4^n)
Space	O(n * 4^n)

Time is O(n * 4^n) in the worst case. Each digit maps to at most 4 letters (digits 7 and 9), so the tree has at most 4^n leaves. Building each combination string takes O(n) time. In practice, most digits map to 3 letters, so the average case is closer to O(n * 3^n).

Space is O(n * 4^n) for storing all combinations in the result list. The recursion stack uses O(n) additional space (one frame per digit). If you ignore the output, the extra space is just O(n).

Edge cases

Before submitting, check these:

Empty input: digits = "". Should return [], not [""]. The problem specifies an empty list for empty input.
Single digit: digits = "2". Should return ["a", "b", "c"]. Good sanity check.
Digit 7 or 9: These map to 4 letters instead of 3. Make sure your mapping includes "pqrs" and "wxyz".
Maximum length: The constraint says digits has at most 4 characters. So the maximum output size is 4^4 = 256 combinations, which is trivial.

The building blocks

This problem is built on one core reusable piece that CodeBricks drills independently.

Choose-explore-unchoose (backtracking template)

The same skeleton that powers Permutations, Subsets, Word Search, and every other backtracking problem:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)      # choose
        backtrack(state)          # explore
        undo_choice(choice)       # unchoose

In the letter combinations solution, candidates(state) is phone[digits[i]], the letters mapped to the current digit. make_choice is appending a letter (or concatenating it to a string). undo_choice is popping it (or relying on string immutability). The base case triggers when every digit has been assigned a letter.

This same template handles:

Permutations: candidates are unused elements, and every element must be placed.
Subsets: candidates are "include or skip" for each element.
Combination Sum: candidates allow reuse by recursing with i instead of i + 1.
Word Search: candidates are the 4 neighbors of the current cell on a grid.

The key insight is that letter combinations of a phone number uses the exact same recursive structure as these other problems. The only thing that changes is where the candidates come from (a digit-to-letter mapping) and what constitutes a complete solution (all digits processed).

A common mistake is forgetting the empty-input check. If digits is empty and you call backtrack(0, ""), the base case immediately fires and records "", giving you [""] instead of []. Always handle the empty case before starting recursion.

Common mistakes

1. Forgetting the empty-input guard. Without if not digits: return [], you get [""] for empty input. The problem expects [].

2. Wrong digit-to-letter mapping. Digit 1 maps to nothing. Digit 0 maps to nothing. Only 2-9 have letters. If the problem says "digits from 2-9," your mapping only needs those 8 entries.

3. Off-by-one on the digit index. Make sure you increment i by 1, not by the length of the letter group. You process one digit per recursion level regardless of how many letters that digit maps to.

4. Returning strings instead of a list of strings (or vice versa). The return type is list[str]. Each element is a multi-character string like "ad", not a list of characters.

When to use this pattern

Look for these signals:

The problem asks for all combinations built by choosing one option from each of several groups
Each "slot" in the result has a fixed set of candidates
The candidates come from a mapping or lookup table
The total number of results is the product of the group sizes (small enough to enumerate)

Problems that use the same backtracking combinations pattern:

Permutations (LeetCode 46): same choose-explore-unchoose, but candidates are unused elements instead of mapped letters
Subsets (LeetCode 78): same template, but the choice is include/skip rather than picking from a group
Combination Sum (LeetCode 39): similar branching, but with a target constraint and element reuse
Generate Parentheses (LeetCode 22): each position has candidates ("(" or ")") subject to validity constraints

From understanding to recall

You see how the backtracking tree branches at each digit and how each path produces one combination. The choose-explore-unchoose pattern is the same one you have seen in Permutations and Subsets. But can you write the digit mapping and the backtracking function from scratch in under two minutes?

That is what interviews require. LeetCode 17 is a medium-difficulty problem, but under time pressure, people fumble the mapping dictionary, mix up the digit index with the letter index, or forget the empty-input guard. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the backtracking letter combinations solution from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "letter combinations phone number" and the code flows out without hesitation.

The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Permutations - The same choose-explore-unchoose template applied to generating all arrangements. Compare how "which element goes in this position" differs from "which letter does this digit produce."
Subsets - The simplest backtracking problem. Useful for seeing how the template adapts when the branching decision is "include or skip" instead of "pick one from a group."
Word Search - Grid backtracking using the same template. Shows how choose-explore-unchoose adapts to 2D navigation with visited-cell tracking.

CodeBricks breaks Letter Combinations into its choose-explore-unchoose building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.

Try CodeBricks free