Letter Combinations of a Phone Number
Last Updated: April 1, 2026
Understanding the Problem
We need to generate every possible string that a sequence of phone digits could represent. Each digit maps to a set of letters (like an old phone keypad), and we need to pick one letter per digit and combine them in order.
The important observation is that this is a Cartesian product. If the input is "23", digit 2 gives us {a, b, c} and digit 3 gives us {d, e, f}. The answer is every way to pick one element from each set, preserving the order of digits. That is 3 x 3 = 9 combinations.
Unlike problems like Subsets or Permutations where we choose from a single pool, here each position in the result draws from a different pool of letters. The length of every output string is exactly the number of digits in the input, so there is no variable-length decision to make. We just need to systematically explore all choices.
Key Constraints:
0 <= digits.length <= 4— The maximum number of digits is 4. Since each digit maps to at most 4 letters (digits 7 and 9), the maximum number of combinations is 4^4 = 256. This is tiny. Any approach will work.digits[i]is in range['2', '9']— No need to handle digits 0 or 1, which do not map to letters.
Approach 1: Iterative BFS-Style
Intuition
The most direct way to think about this is layer by layer. Start with an empty string. For the first digit, generate all single-character strings from its letters. For the second digit, take each existing string and append each letter of the second digit. Keep going until all digits are processed.
This is essentially a breadth-first expansion. At each step, the number of partial combinations multiplies by the number of letters the current digit maps to. It is simple to implement with a list and does not require recursion.
Algorithm
- Create a mapping from each digit to its letters.
- Initialize a list of results with a single empty string
[""]. - For each digit in the input, create a new empty list. For each existing combination, append each letter of the current digit to get new combinations. Replace the current list with the new list.
- Return the final list. If the input is empty, return an empty list immediately.
Example Walkthrough
Code
- Time Complexity: O(n * 4^n). Where n is the length of digits. Each digit maps to at most 4 letters, so there are up to 4^n total combinations. Building each combination involves O(n) string concatenation.
- Space Complexity: O(4^n). We store all combinations in the result list at every step. At the final step, there are up to 4^n combinations.
The iterative approach works, but it creates many intermediate string objects at each layer. Can we build combinations more naturally using recursion, exploring one digit at a time?
Approach 2: Backtracking (Optimal)
Intuition
Instead of building combinations layer by layer, we can think recursively. Process one digit at a time: for the current digit, pick one of its letters, add it to the combination being built, and recurse on the remaining digits. When we have processed all digits, we have a complete combination.
This is the classic backtracking pattern. Each recursive call represents "I'm at digit index i, and I've built this prefix so far. Let me try each letter for digit i." The recursion naturally explores the entire decision tree, and every root-to-leaf path corresponds to one valid combination.
The backtracking approach works because it systematically explores the entire decision tree. At each digit position, we have a fixed set of choices (the letters mapped to that digit). By trying each choice and recursing, we guarantee that every path through the tree is visited exactly once. There is no pruning needed here since every branch leads to a valid combination.
Algorithm
- Create a mapping from each digit to its letters.
- Start a recursive function with index 0 and an empty string as the current combination.
- Base case: if the index equals the length of digits, add the current combination to results.
- Recursive case: get the letters for
digits[index]. For each letter, append it to the current combination and recurse withindex + 1. - Return the collected results.
Example Walkthrough
Code
- Time Complexity: O(n * 4^n). Where n is the length of digits. The recursion tree has at most 4^n leaves. At each leaf, we create a string of length n, costing O(n).
- Space Complexity: O(n). The recursion stack goes n levels deep. The current combination being built takes O(n) space. The output is not counted as auxiliary space.