17. Letter Combinations Of A Phone Number

When candidates first encounter this problem, they often recognize that it involves generating combinations but struggle with the mechanics of building strings across multiple groups of characters. The real challenge is understanding how to systematically explore every possible path through a branching decision tree without missing or duplicating any combination. This problem is a textbook exercise in backtracking, which is a core pattern behind subset generation, permutation problems, and constraint satisfaction tasks that appear frequently in interviews.

Problem statement

Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent on a standard telephone keypad. The mapping of digits to letters follows the classic phone layout:

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

Each digit in the input string contributes one letter to each output combination. The answer can be returned in any order. If the input string is empty, return an empty list.

Note that the digit 1 does not map to any letters on a phone keypad.

Constraints

• 0 ≤ digits.length ≤ 4
• digits[i] is a digit in the range ['2', '9']

Examples

Why enumerating all possibilities doesn’t scale

At first glance, you might think about generating every possible string of the correct length and then filtering to keep only valid ones. But the number of strings you would need to check grows dramatically. Each digit contributes 3 or 4 possible letters, so with n digits the total number of valid combinations is up to 4^n. If you tried to enumerate strings over the entire alphabet and then verify each one, you would waste enormous effort on invalid candidates.

Even within the valid combinations, a naive iterative approach that builds partial results using nested loops becomes unwieldy as the number of digits increases. With four digits where each maps to four letters, you would need four nested loops, and the structure would not generalize to arbitrary input lengths. The problem demands a recursive strategy that naturally adapts to any number of digits.

Optimized approach

The ideal strategy is backtracking, which is a controlled form of recursion where you build a candidate solution one decision at a time and undo each decision after fully exploring its consequences. Here, each “decision” is choosing which letter to use for the current digit.

Think of the problem as a tree. The root represents an empty string. At depth 0, you branch into the letters for the first digit. At depth 1, each of those branches splits again into the letters for the second digit, and so on. Every path from root to a leaf at depth n (where n is the number of digits) represents one valid combination. Backtracking walks this entire tree, collecting every leaf.

This pattern fits naturally because:

• Each digit position is an independent choice.
• The choices at one level do not constrain choices at other levels.
• We need every valid combination, not just one.

Why the optimized approach works well

Backtracking visits exactly the combinations that matter. It never generates an invalid partial string because every path through the tree corresponds to a valid selection of one letter per digit. The “undo” step (popping the last letter from the current path) ensures the algorithm reuses a single mutable path structure rather than allocating new strings at every step, keeping memory overhead low.

Because the total output size is O(4^n) and each combination has length n, the algorithm does O(n * 4^n) total work, which matches the size of the output itself. You cannot do better than this since every combination must appear in the result.

Step-by-step algorithm

1. If the input string digits is empty, return an empty list immediately.
2. Create a dictionary that maps each digit character ('2' through '9') to its corresponding list of letters.
3. Initialize an empty list combinations to store the final results.
4. Define a recursive function backtrack(index, path) where index is the current position in digits and path is the list of letters chosen so far.
5. Inside backtrack, if the length of path equals the length of digits, join path into a string, append it to combinations, and return.
6. Otherwise, look up the letters corresponding to digits[index].
7. For each letter in that group, append the letter to path, recursively call backtrack(index + 1, path), and then remove the last letter from path to undo the choice.
8. Start the recursion by calling backtrack(0, []).
9. Return combinations.

1 / 12

Python implementation

def letter_combinations(digits):
    # Return early for empty input
    if not digits:
        return []

    # Phone keypad mapping from digit to letters
    digit_to_letters = {
        "2": ["a", "b", "c"],
        "3": ["d", "e", "f"],
        "4": ["g", "h", "i"],
        "5": ["j", "k", "l"],
        "6": ["m", "n", "o"],
        "7": ["p", "q", "r", "s"],
        "8": ["t", "u", "v"],
        "9": ["w", "x", "y", "z"],
    }

    combinations = []

    def backtrack(index, path):
        # A complete combination has been formed
        if len(path) == len(digits):
            combinations.append("".join(path))
            return

        # Get letters for the current digit
        for letter in digit_to_letters[digits[index]]:
            path.append(letter)
            backtrack(index + 1, path)
            # Undo the choice before trying the next letter
            path.pop()

    backtrack(0, [])
    return combinations


# Driver code with 5 test cases
if __name__ == "__main__":
    test_cases = ["23", "", "79", "8", "234"]

    for i, digits in enumerate(test_cases, 1):
        result = letter_combinations(digits)
        print(f"Test {i}: digits = \"{digits}\"")
        print(f"  Result: {result}")
        print("-" * 80)

Time complexity

Let n be the length of the input string digits. Each digit maps to either 3 or 4 letters, so in the worst case every digit maps to 4 letters. The total number of combinations is at most 4^n, and each combination is a string of length n. Building and storing each string takes O(n) time. Therefore the overall time complexity is O(n * 4^n). Given the constraint that n ≤ 4, this amounts to at most 4 * 256 = 1024 character operations, which is trivially fast.

Space complexity

The output list stores up to 4^n strings, each of length n, giving O(n * 4^n) space for the results. Beyond the output, the recursion stack goes at most n levels deep, and the mutable path list holds at most n characters. So the auxiliary space (excluding the output) is O(n). With n ≤ 4, the recursion depth is negligible.

Edge cases

• Empty input string: When digits is "", there are no digits to process. The function should return an empty list [], not a list containing an empty string.
• Single digit: When digits contains only one character like "7", the result is simply the individual letters for that digit: ["p", "q", "r", "s"]. No cross-product is needed.
• All four-letter digits: An input like "79" (or "7979" at the constraint limit) produces the maximum branching factor at every level. This tests that the solution handles the upper bound of output size correctly.

Common pitfalls

• Returning [""] instead of [] for empty input: Many candidates forget the empty check and let the recursion produce a single empty string from an empty path, which is incorrect.
• Forgetting to pop after the recursive call: Without the undo step, the path list accumulates letters from previous branches, producing garbled results. This is the most common backtracking mistake.
• Using string concatenation instead of a list: Building a new string at every recursive call creates unnecessary intermediate objects. Using a mutable list with append and pop is more efficient and idiomatic for backtracking.
• Hardcoding nested loops: Some candidates write nested for loops to handle two or three digits, which breaks when the input length changes. The recursive approach generalizes to any number of digits.