Given a string digits containing digits from 2 to 9, return every letter combination the number could spell. The combinations may be returned in any order.
The digit-to-letter mapping is the one on a telephone keypad: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz. Note that 1 maps to no letters and never appears in the input.
If digits is the empty string, return an empty array.
Example
2 → "abc" and 3 → "def"; every pairing of one letter from each gives 3 × 3 = 9 combinations.
Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range '2' to '9'.
Intuition
A first attempt builds the whole cartesian product a round at a time: start with just the empty combination, and for each digit in turn, extend every combination built so far with every letter that digit could be.
function letterCombinations(digits) {
// No digits, no combinations.
if (digits.length === 0) return [];
const map = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
};
// The "product built so far" — starts as just the empty combination.
let combos = [""];
for (const digit of digits) {
const letters = map[digit];
const next = [];
// Extend every combination built so far with every letter this digit could be.
for (const combo of combos) {
for (const letter of letters) {
next.push(combo + letter);
}
}
combos = next; // this round's full product replaces the last one entirely
}
return combos;
}This already runs in O(n · 4ⁿ) — the same order as the optimal, since the output itself holds up to 4ⁿ combinations of length n, and no algorithm that returns every one of them can do less work than that. Can we do better?
Not on complexity — on how directly the choices get made. Every round, the outer loop throws combos away and rebuilds next from scratch, re-copying every prefix built in every earlier round just to tack one more letter onto it. That's the same fix-one-choice-then-recurse-into-the-rest idea behind Subsets and Permutations, just run breadth-first over the whole frontier of partial strings instead of depth-first over one path at a time — and depth-first only ever needs one partial string in memory (the call stack's local path), not every combination built so far.
The stored solution takes that route: walk the digits left to right with an index and a single path string built one character at a time. At each index, try every letter digits[index] maps to — recurse into index + 1 with path + letter — and once index reaches digits.length, path is a complete combination, so record it. Because path + letter builds a new string rather than mutating a shared one, there's no explicit undo step the way an array-based path.pop() would need — the caller's own path is untouched by whatever the recursive call did with its copy.
Walking it through:
digits = "352"
Start at index 0 with an empty path. Digit '3' maps to "def"; try its first letter.
One level deeper on the 'd' branch. Digit '5' maps to "jkl"; try its first letter.
Index 2 is digit '2', which maps to "abc"; try its first letter. The path is now three characters long — one per digit.
The path's length now matches digits.length, so "dja" is a complete combination — record it, then return back up to where 'a' was chosen.
Back at index 2, drop 'a' and try digit '2''s next letter, 'b' — that completes another combination, "djb".
Once all three of digit '2''s letters (a, b, c) are tried under "dj", unwind to index 1 and move to digit '5''s next letter, 'k'. A fresh descent into index 2 begins again from there.
Optimization
Backtracking
Walk the digits left to right, building one combination character by character. At digit index i, try each letter that digit maps to, append it, recurse to i + 1, then drop it. When the path length equals digits.length it's a complete combination — record it. The empty input is handled up front by returning [].
If n is the number of digits, there are up to 4^n combinations and each takes O(n) to assemble, so O(n · 4^n) time and O(n) recursion depth.
function letterCombinations(digits) {
// No digits, no combinations — return immediately rather than descending into an empty recursion.
if (digits.length === 0) return [];
// Telephone keypad: each digit 2-9 maps to the letters it could represent.
const map = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
};
const result = [];
// index: which digit position we're deciding next; path: the combination built so far.
const backtrack = (index, path) => {
// Base case: a letter has been chosen for every digit — path is a complete combination.
if (index === digits.length) {
result.push(path);
return;
}
// Try every letter this digit could be, recursing one position deeper for each choice.
for (const letter of map[digits[index]]) {
backtrack(index + 1, path + letter);
}
};
backtrack(0, "");
return result;
}Complexity analysis
Time complexity: O(n · 4ⁿ). Here's why:
- Each digit maps to at most 4 letters (
7and9), so the recursion branches at most 4 ways at every position, giving at most 4ⁿ complete combinations forndigits. - Reaching each leaf takes
nrecursive calls — one per digit position — and recording it involves a string of lengthn, both O(n) of work per leaf. - There's no wasted work above the leaves: every call either recurses further or returns immediately, so the total cost tracks the leaves times their depth.
So the overall time is 4ⁿ × O(n) = O(n · 4ⁿ).
Space complexity: O(n) auxiliary. Here's why:
- The recursion stack is at most
nframes deep, one per digit position. - Each call's own
pathargument is a string of length up ton; because strings are immutable, there's no shared mutable buffer to undo on the way back up. - The digit-to-letters
mapis a fixed 8-entry table — O(1) regardless of the input.
So the extra bookkeeping is O(n). The result array itself holds up to 4ⁿ strings of length n — O(n · 4ⁿ) — but that's the required output, not overhead the algorithm adds.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| digits = "8" | ["t","u","v"] | Single digit — smallest nonempty input, a three-letter set. |
| digits = "35" | ["dj","dk","dl","ej","ek","el","fj","fk","fl"] | Two digits, three letters apiece — a fresh two-digit spread not shown in the example. |
| digits = "44" | ["gg","gh","gi","hg","hh","hi","ig","ih","ii"] | The same digit twice — every letter pairs with every letter, including itself. |
| digits = "94" | ["wg","wh","wi","xg","xh","xi","yg","yh","yi","zg","zh","zi"] | A four-letter digit paired with a three-letter digit — an asymmetric letter-set size. |
| digits = "638" | ["mdt","mdu","mdv","met","meu","mev","mft","mfu","mfv","ndt","ndu","ndv","net","neu","nev","nft","nfu","nfv","odt","odu","odv","oet","oeu","oev","oft","ofu","ofv"] | Three digits — same depth as the walkthrough, one deeper than the derived example. |
Try it yourself
Write your solution against the real judge before checking the reference.