Letter Combinations of a Phone Number
- 2 days ago
- 7 min read
Letter Combinations looks simple on the surface - press some phone keys, get some letters. But underneath, it's a classic interviewers test for whether you can systematically explore combinations without losing control of the recursion. If you've been building up your backtracking intuition through Subsets and Combination Sum, this problem will feel familiar in structure but different in flavor. It's worth understanding exactly why.
Problem Statement
Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. The mapping follows the standard telephone keypad.
Each digit maps to a fixed set of letters.
Choose exactly one letter per digit.
Return all possible combinations in any order.
If the input is empty, return an empty list.
Examples:
"23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]
"2" → ["a","b","c"]
"" → []
1. Clarify Requirements Before Jumping Into Code
Before writing anything, make sure the rules are clear.
Input: A string of digits, each between 2 and 9.
Output: All possible letter combinations - one letter chosen per digit, in any order.
Key details to confirm:
Digits 0 and 1 don't appear, since they have no letter mappings.
Empty input returns [], not [""]. There's a meaningful difference: [""] says there's one combination (the empty string), while [] says there are no combinations at all.
This is combination generation, not phone number validation.
2. Identify the Category of the Problem
This is a backtracking problem, but it has a different character than what you've seen before.
In Subsets and Combination Sum, the choices at each level came from the same pool. You were deciding which elements from nums or candidates to include. Here, each position has its own fixed set of choices determined entirely by which digit sits at that position. The first digit tells you which letters are available at level 0. The second digit tells you which letters are available at level 1. And so on.
This makes the problem simpler in one sense - there's no overlap between levels, no need for a start index to prevent duplicates, no reuse logic to manage. Each level is completely independent. You just need to systematically try every option at each level and combine them.
3. Start With Brute Force to Build Intuition
Imagine building combinations by hand for "23". Digit 2 maps to abc and digit 3 maps to def.
You might start by listing all letters for the first digit:
a, b, cThen for each of those, append every letter from the second digit:
a → ad, ae, af
b → bd, be, bf
c → cd, ce, cfThis is iterative expansion, the same approach we saw as an alternative in Subsets. It works, but as digits increase it becomes increasingly awkward to manage nested loops. For a three-digit input you'd need three loops. For four digits, four loops. The structure doesn't scale.
What you want instead is a general mechanism that handles any number of digits with the same code. That's exactly what recursion gives you.
4. Brainstorm More Solutions
Step 1: Visualize the Problem as a Tree
Draw out what happens with "23":
root
/ | \
a b c ← choices for '2'
/ | \ / | \ / | \
d e f d e f d e f ← choices for '3'Every path from root to leaf is a valid combination. The tree has exactly as many leaves as there are combinations - 3 × 3 = 9 for "23", 3 × 3 × 3 = 27 for "234", even up to 4 × 4 = 16 for inputs involving digits 7 or 9 (which map to four letters).
This tree visualization reveals the recursive structure immediately. Each level corresponds to one digit. Each node branches into the letters for that digit. DFS over this tree - picking one letter per level and recording the full path at each leaf - generates all combinations.
Step 2: Define the Recursive State
What does each recursive call need to know?
index: Which digit we're currently processing. This tells us which letters are available at this level and when we're done (when index == digits.length()).
path: The combination built so far - one letter chosen from each digit we've processed.
That's it. No used array, no start index, no remaining target. The state is minimal because the problem is structured: each level's choices are fixed and independent.
At each call:
If index == digits.length(): we've chosen one letter for every digit, so record the combination and return.
Otherwise: look up the letters for digits[index], loop through them, add each to path. Next, recurse with index + 1. And finally, remove it.
Step 3: Trace Through an Example
Let's trace "23" completely:
backtrack(index=0, path="")
letter='a': backtrack(index=1, path="a")
letter='d': backtrack(index=2, path="ad") → record "ad"
letter='e': backtrack(index=2, path="ae") → record "ae"
letter='f': backtrack(index=2, path="af") → record "af"
letter='b': backtrack(index=1, path="b")
letter='d': backtrack(index=2, path="bd") → record "bd"
letter='e': backtrack(index=2, path="be") → record "be"
letter='f': backtrack(index=2, path="bf") → record "bf"
letter='c': backtrack(index=1, path="c")
letter='d': backtrack(index=2, path="cd") → record "cd"
letter='e': backtrack(index=2, path="ce") → record "ce"
letter='f': backtrack(index=2, path="cf") → record "cf"Nine combinations, perfectly matching the tree diagram. Notice how clean the recursion is - no duplicate checking, no pruning decisions, no boundary conditions beyond the index check. The structure of the problem does all the work.
Step 4: How Does This Differ From What You've Seen Before?
It's worth pausing to compare this to previous backtracking problems.
In Subsets, the choices at each level came from the same array, and you used a start index to avoid generating the same subset twice.
In Combination Sum, you had to decide whether to include each element and manage a running target.
Here, there's no shared pool of choices. Each digit dictates exactly what's available at its level, and those choices are completely separate from every other level. There are no duplicates to skip, no reuse decisions to make, no pruning conditions to check. The backtracking is at its purest: choose one option from a fixed set, recurse deeper, undo the choice.
Step 5: Is There an Iterative Alternative?
Recursive solutions often have an iterative alternative. Does this one?
Yes. Iterative expansion works here exactly as it did in Subsets.
Start with [""]. For each digit, take every string built so far and create new versions with each of that digit's letters appended:
Start: [""]
After '2': ["a", "b", "c"]
After '3': ["ad","ae","af","bd","be","bf","cd","ce","cf"]This is clean and avoids recursion entirely. The tradeoff: you're storing all intermediate combinations in memory as you go - O(4ⁿ) space at peak. The recursive approach uses O(n) stack space (one frame per digit) and only stores combinations as they're completed.
For short digit strings (the problem typically constrains input length to 4 or fewer), either approach is fine. In an interview, backtracking is the better answer because it demonstrates the more general skill.
5. Trade-Offs at a Glance
Approach | Time | Space | Notes |
Iterative expansion | O(4ⁿ × n) | O(4ⁿ × n) | No recursion; high intermediate memory |
Backtracking (DFS) | O(4ⁿ × n) | O(n) | Clean, minimal stack space, preferred |
The O(4ⁿ) factor reflects the maximum number of combinations - 4 letters per digit (for digits 7 and 9) across n digits. The O(n) factor accounts for copying each completed string of length n into the result. Stack space is O(n) - one frame per digit.
6. Pseudocode
if digits is empty:
return []
build phoneMap: digit → letters string
result = empty list
backtrack(index, path):
if index == digits.length:
add path as string to result
return
for each letter in phoneMap[digits[index]]:
append letter to path
backtrack(index + 1, path)
remove last letter from path
call backtrack(0, empty path)
return result7. Edge Cases
Empty input: Check at the start and return [] immediately. Don't let the recursion run - it would add an empty string to results, which is wrong.
Single digit: One level of recursion, recording each letter as a complete combination. Output has 3 or 4 strings.
Digits 7 or 9: These map to four letters (pqrs, wxyz). Make sure your phone map is correct - it's an easy place to introduce a bug. For an all-7s or all-9s input, the output is 4ⁿ combinations.
8. Full Solution
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class LetterCombinations {
private static final Map<Character, String> phoneMap = new HashMap<>();
static {
phoneMap.put('2', "abc");
phoneMap.put('3', "def");
phoneMap.put('4', "ghi");
phoneMap.put('5', "jkl");
phoneMap.put('6', "mno");
phoneMap.put('7', "pqrs");
phoneMap.put('8', "tuv");
phoneMap.put('9', "wxyz");
}
public static List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) {
return result;
}
backtrack(digits, 0, new StringBuilder(), result);
return result;
}
private static void backtrack(String digits, int index,
StringBuilder path,
List<String> result) {
if (index == digits.length()) {
// snapshot the current combination
result.add(path.toString());
return;
}
String letters = phoneMap.get(digits.charAt(index));
for (char c : letters.toCharArray()) {
path.append(c); // choose
backtrack(digits, index + 1, path, result); // explore
path.deleteCharAt(path.length() - 1); // un-choose
}
}
}One implementation note: we use StringBuilder instead of String for path because String is immutable in Java - appending to it creates a new object each time. StringBuilder gives us efficient in-place append and delete, which is exactly what backtracking needs.
9. Test Your Solution
System.out.println(letterCombinations(""));
// [] — not [""]
System.out.println(letterCombinations("2"));
// [a, b, c]
System.out.println(letterCombinations("23"));
// [ad, ae, af, bd, be, bf, cd, ce, cf]
System.out.println(letterCombinations("79"));
// 16 combinations — both digits map to 4 letters
System.out.println(letterCombinations("234").size());
// 27 — 3 × 3 × 310. Key Lessons for Future Problems
When each position has a fixed, independent set of choices, think DFS with an index. The key signal here is that there's no shared pool of candidates being consumed - each level is entirely determined by the digit at that position. That's different from Subsets or Combination Sum, where choices at each level depend on what's already been chosen. Recognizing this distinction helps you immediately reach for the simpler recursive structure.
Visualize the recursion tree before writing code. Drawing even two levels of the tree for "23" makes the structure obvious. The tree has as many levels as there are digits and branches at each level equal to the number of letters for that digit. Once you see it, the code almost writes itself.
Know the whole backtracking family. You've now seen the pattern applied across multiple problems. The skeleton is always the same - choose, explore, un-choose. What varies is where choices come from, when results get recorded, and what constraints exist. Letter Combinations is the cleanest version of the pattern: no duplicate handling, no reuse decisions, no convergence conditions. It's backtracking in its purest form, which makes it an ideal problem to revisit when you want to refresh your intuition before a harder problem.
Letter Combinations is simple by design. But "simple" doesn't mean unimportant - it means the problem isolates the core skill without adding noise. Nail the fundamentals here, and everything harder is just a variation on what you already understand.
Good Luck and Happy Coding!
Comments