Given a string digits containing digits from 2 to 9, return all the letter combinations the number could spell — one letter chosen for each digit, just like typing a word on an old phone keypad.
The keypad mapping is the classic one: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz. The digits 0 and 1 map to no letters. You may return the combinations in any order.
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] Digit 2 offers a, b, c and digit 3 offers d, e, f; pairing every choice gives nine words.
Input: digits = "2" Output: ["a","b","c"]
- 1 <= digits.length <= 4 - digits[i] is a digit in the range ['2', '9'].
Every phone keypad hides a tiny combinatorics puzzle: press a few digits and each one offers a handful of letters. Turning those choices into every possible word is our first real taste of building combinations systematically.
O(1).In plain words: each digit maps to a set of letters; produce every string formed by choosing one letter for each digit, keeping the digits in order.
Worked example — digits = "23"
2 → a b c 3 → d e f pick one from each course: a+d a+e a+f b+d b+e b+f c+d c+e c+f → ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Asking these before coding shows you think about edge cases the way a senior engineer does.
“Can the input be empty?”
An empty string should return an empty list, not a list containing one empty string.
“Do the digits 0 and 1 ever appear?”
They map to no letters, so confirming they are excluded keeps the mapping clean.
“Does the order of the combinations matter?”
Any order is accepted, which frees us to build them in whatever order is simplest.
“How long can the digit string get?”
With at most 4 digits the result is tiny (at most 81 words), so we can safely enumerate everything.
Before I code, a few quick clarifications.
First, if the input is empty I will return an empty list rather than a blank string.
And since any order is fine, I will build the combinations digit by digit.
Each digit contributes an independent set of letters, and a combination picks exactly one from each. So the total count is those sizes multiplied together — 3 × 3 = 9 for "23" — and never more than 4^n.
If you already have every combination for the first k digits, the next digit just multiplies the list: each existing prefix spawns one child per new letter.
[""] --2--> [a,b,c] --3--> [ad,ae,af,bd,be,bf,cd,ce,cf]
Instead of storing every partial list, walk the choices depth-first with a single buffer: append a letter, recurse, then pop it. You only ever hold one in-progress string plus the finished output.
| Iterative product | Backtracking | |
|---|---|---|
| Time | O(4^n · n) | O(4^n · n) |
| Extra space | O(4^n · n) | O(n) |
| Idea | multiply the frontier list | one buffer, DFS |
Both enumerate exactly the same combinations; backtracking simply keeps memory down to a single path. The full code for each is in the Approaches selector below.
Key takeaway
Generating "all combinations of independent choices" is a Cartesian product. Backtracking — pick, recurse, undo — walks that product with one reusable buffer, and it is the template behind subsets, permutations, and combination-sum.
backtrack(i, path):
if i == len(digits):
record path
return
for letter in map[digits[i]]:
add letter to path
backtrack(i + 1, path)
remove letter from path