Loading…

mediumBacktrackingLC #17Asked very often

Letter Combinations of a Phone Number

Backtracking · 6 of 13 · 9 min

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz

In plain English

Each digit independently contributes one letter chosen from its 3-or-4-letter alphabet, and a combination is one letter from each digit concatenated in order. So the answer is the Cartesian product of the per-digit letter sets. With up to 4 digits each offering up to 4 letters, there are at most 4⁴ = 256 combinations. The empty input is special: zero digits means zero combinations, so we return [].

Examples

Example 1

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Note: Digit 2 → {a,b,c}, digit 3 → {d,e,f}. Every pairing gives 3 × 3 = 9 combinations.

Example 2

Input: digits = ""
Output: []
Note: No digits means no combinations. Return an empty list, NOT [""].

Example 3

Input: digits = "2"
Output: ["a","b","c"]
Note: A single digit 2 yields its three letters directly.

Constraints

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

Clarifying questions4First question: What should an empty input string return?Explore questions

Q1.What should an empty input string return?
An empty list []. There are no digits, hence no letters to combine. Returning [""] (a list with one empty string) is the classic wrong answer — guard it explicitly.
Q2.Do digits 0 and 1 ever appear?
No — the constraint restricts digits to 2–9. 0 and 1 have no letters, so we never need to map them.
Q3.Does the order of the output combinations matter?
No, any order is accepted. Within each combination, order is fixed: the i-th character comes from the i-th digit.
Q4.How long can the digit string be?
At most 4 digits, so at most 4⁴ = 256 combinations. The space is tiny; the focus is on a clean product enumeration.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Map each digit to its phone letters and return every string formed by picking one letter per digit — a Cartesian product. The canonical answer is backtracking: at digit `index`, loop over that digit's letters, choose one, recurse to `index + 1`, then un-choose. Record when `index` reaches the end. Handle the empty input as a special case (return []). The result size is up to 4^n, so any solution is O(n · 4ⁿ).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise the Cartesian-product structure and write a clean index-advancing backtracking that draws from the right per-digit alphabet, plus whether you remember the empty-input guard. Bonus: quoting the 4ⁿ bound and naming the iterative BFS-style build as an alternative.

Where candidates slip

Returning [""] for empty input instead of [], reusing a start index (wrong model — each digit is a distinct position), or forgetting that 7 and 9 have four letters.

How to stand out

Name it as a Cartesian product, handle the empty input explicitly, write the index-advancing choose/explore/un-choose, state the O(n · 4ⁿ) bound, and mention you could also build it iteratively by expanding a frontier of partial strings.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

The Cartesian-product recursion tree

How to read it:Each level corresponds to one digit; each edge picks one of that digit's letters and advances to the next digit. Every leaf (all digits consumed) is a valid combination — there's no pruning.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Backtracking over Digit Positions (Optimal)

TimeO(n · 4ⁿ)SpaceO(n)

The canonical answer. Phrase it as 'one choice-set per digit — pick a letter, recurse to the next digit, un-choose; it's a Cartesian product'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each digit maps to its own small set of letters, and a combination uses one letter from each digit in order. What familiar structure is 'one choice from each of several independent sets'?

2Hint 2Explore hint

Walk the digits left to right with an `index`. At each level, loop over the letters of `digits[index]`, append one, recurse to `index + 1`, then pop.

3Hint 3Explore hint

Record the built string when `index` reaches the end. Don't forget: if the input is empty, return [] before you even start.

A · Core idea

Treat the digit string as a sequence of independent positions. Walk it with an index; at each call, look up the letters for digits[index], and for each such letter: choose it (append to the path), explore by recursing to index + 1, then un-choose (pop). When index == len(digits) the path holds one letter per digit, so we record the built string.

Why this is a Cartesian product, and why that matters. Each digit offers a fixed alphabet that doesn't depend on what we picked for earlier digits. So the set of answers is exactly {one letter from digit 0} × {one letter from digit 1} × … — the Cartesian product of the per-digit sets. Recognising this tells you two things instantly: there's no pruning (every combination of choices is valid), and the count is the product of the set sizes (3 or 4 each). The recursion is just a systematic enumeration of that product.

Why we advance by digit index, not a start index. In Subsets/Combinations a start index moves through one shared set, skipping forward to avoid duplicates. Here each position has its own set, and we must use every digit exactly once in order. So the recursion variable is the digit index, and we always go to index + 1 after choosing — never reusing a digit, never skipping one. The 'choice-set' changes from level to level (digit 2's letters, then digit 3's), which is the structural difference from single-set problems.

Why the empty-input guard is essential. If digits is empty, the correct answer is [] — there are no digits, so there are no letter combinations. But a naive backtracking that starts by recording at index == 0 == len(digits) would record the empty string and return [""], a list containing one (empty) combination. That's semantically wrong, and it's the single most common bug on this problem, so we special-case empty input up front.

Why a copy/built string at the leaf. The path is a mutable buffer (a StringBuilder in Java, a list in Python) shared across the whole tree. At a leaf we materialise it with toString() / ''.join(path), which produces a fresh immutable string — safe to store. The subsequent pop()/deleteCharAt then rewinds the buffer for sibling branches without affecting the strings we already saved.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

digits = "23"

Interactive diagram

Choose / explore / un-choose for "23"

index=0

Active call / nodeSupporting contextReturned stateNot active

Level 0 draws from {a,b,c}, level 1 from {d,e,f}. Every leaf is a valid combination — no branch is ever pruned.

Final result["ad","ae","af","bd","be","bf","cd","ce","cf"]

C · Code with teaching comments

solution.javaJava

Backtracking over Digit Positions (Optimal) — optimal

8 teaching notes

1
public List<String> letterCombinations(String digits) {
2
    List<String> results = new ArrayList<>();
3
    // The crucial guard — no digits means no combinations, so return [] (never [""]).
4
    if (digits == null || digits.isEmpty()) return results;   // empty input → []
5
    // Index by the digit value: indices 0 and 1 are empty placeholders so digit d maps
6
    // to map[d].
7
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
8
    backtrack(digits, 0, map, new StringBuilder(), results);
9
    return results;
10
}
11
 
12
private void backtrack(String digits, int index, String[] map,
13
                       StringBuilder path, List<String> results) {
14
    // Base case: one letter has been chosen for every digit — a complete combination.
15
    if (index == digits.length()) {
16
        // toString() materialises an immutable snapshot; later deleteCharAt won't
17
        // affect it.
18
        results.add(path.toString());          // all digits used → record built string
19
        return;
20
    }
21
    // `- '0'` converts the char digit to its int value to index the map; the alphabet
22
    // changes per position.
23
    String letters = map[digits.charAt(index) - '0'];   // this digit's alphabet
24
    for (int i = 0; i < letters.length(); i++) {
25
        // CHOOSE: commit one letter of the current digit.
26
        path.append(letters.charAt(i));                 // choose
27
        // Always advance to index+1 — every digit is used exactly once, in order.
28
        backtrack(digits, index + 1, map, path, results); // explore next digit
29
        // UN-CHOOSE: rewind the buffer so the next sibling letter starts from the same
30
        // prefix.
31
        path.deleteCharAt(path.length() - 1);           // un-choose
32
    }
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n · 4ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The 'one choice-set per position' shape is the template for any Cartesian-product enumeration: dice rolls, license-plate generators, expanding a grammar's alternatives. The only moving part versus Subsets is that the loop's alphabet depends on the current position, and you advance to the next position unconditionally instead of using a start index to dodge duplicates.

ComplexityO(n · 4ⁿ) time, O(n) space — Let n be the number of digits. Each digit branches into up to 4 letters, so there are up to 4ⁿ leaves; building each combination string costs O(n). Total time is O(n · 4ⁿ). Extra space beyond the output is the recursion depth and the path buffer, both O(n).

E · Edge cases and pitfalls6digits = "" — Caught by the guard → returns [] immediately, never entering the recursion (avoids the [""] bug).Explore edge cases

Edge cases handled

digits = ""Caught by the guard → returns [] immediately, never entering the recursion (avoids the [""] bug).
digits = "79"7→pqrs (4 letters), 9→wxyz (4 letters) → 4 × 4 = 16 combinations. Confirms the 4ⁿ branching, not 3ⁿ.

Pitfalls

Returning [""] for empty input instead of [] — the #1 bug on this problem.
Forgetting the 4-letter alphabets for 7 (pqrs) and 9 (wxyz).
Using a start index as if it were one shared set — each digit is its own position with its own alphabet.
Storing a mutable buffer reference instead of a built string at the leaf.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<String> letterCombinations(String digits) { List<String> results = new ArrayList<>(); if (digits == null || digits.isEmpty()) return results; // empty input → [] String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; backtrack(digits, 0, map, new StringBuilder(), results);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning [""] for empty input

With no digits there are no combinations, so the answer is []. A backtracking that records at index 0 (== len) for empty input emits the empty string, giving [""] — semantically wrong. Guard up front.

Explore the code comparison

Don't write this

def letterCombinations(self, digits):
    results = []
    backtrack(0, [])      # no guard → records "" and returns [""]
    return results

Write this instead

def letterCombinations(self, digits):
    if not digits:
        return []         # guard the empty input
    results = []
    backtrack(0, [])
    return results

Wrong alphabet for 7 and 9

Most digits map to 3 letters, but 7→pqrs and 9→wxyz have 4. A 3-letter-everywhere map silently drops 's' and 'z' from the output.

Explore the code comparison

Don't write this

mapping = {"7": "prs", "9": "wxy"}   # missing 's'/'z' tails!

Write this instead

mapping = {"7": "pqrs", "9": "wxyz"}  # four letters each

Using a start index instead of digit index

A start index belongs to single-set problems (Subsets) where you skip forward to dedup. Here each digit is a distinct position with its own alphabet, so you advance by index and always go to index + 1.

Explore the code comparison

Don't write this

for i in range(start, len(digits)):   # wrong model — one shared set
    for letter in mapping[digits[i]]:
        ...

Write this instead

for letter in mapping[digits[index]]: # current digit's alphabet
    path.append(letter)
    backtrack(index + 1, path)
    path.pop()

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Backtracking over a fixed sequence of choice-sets (Cartesian product)

Code pattern to memorize

def backtrack(index, path):
    if index == len(digits): results.append(''.join(path)); return
    for letter in mapping[digits[index]]:   # one choice-set per digit
        path.append(letter)                 # choose
        backtrack(index + 1, path)          # explore the next digit
        path.pop()                          # un-choose

Rules to remember

1Advance by digit index, not by a start index — every digit contributes exactly one letter, in order.
2The loop is over the current digit's letters; recursion always goes to index + 1 (never reuse the digit).
3Record only at a complete leaf (index == len(digits)) — a combination must use all digits.
4Guard the empty input: digits == "" must return [], not [""] — the most common edge-case miss.
5Use a StringBuilder/list as the path and append a built copy (toString()/''.join) at the leaf.
6Digits 7 and 9 map to 4 letters (pqrs, wxyz); the rest map to 3 — that's why the bound is 4ⁿ, not 3ⁿ.

Use this pattern when

Generate the **Cartesian product** of several independent choice-sets
Each position draws from its own fixed alphabet (digit → letters)
You need all combined strings/tuples, not just a count
The number of positions is small (digit string is short)

Choose another pattern when

Only the **count** of combinations is needed → multiply the choice-set sizes, no enumeration
Choices depend on previous picks (a constraint links positions) → it's not a plain product
The same set is reused and order doesn't matter → that's combinations/subsets, not a product
n is large → 4ⁿ explodes; full enumeration is infeasible

Interview takeaway

This is the 'Cartesian product' member of the backtracking family — the cleanest one, because there's no pruning and no dedup, just one choice-set per position. Master the index-advancing choose/explore/un-choose here and you can generate any product (Combinations of well-formed parentheses, generate-all-from-grammar) with the same skeleton.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Backtracking for a Cartesian product (choose → explore → un-choose) advancing by position with a per-position choice-set. Recognise it whenever each position draws independently from its own fixed alphabet and you need every combined string. The skeleton matches Subsets; the differences are the per-digit alphabet and unconditional advance to index + 1 (no start index, no pruning).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Generate Parentheses
Coming soon
Also builds all strings via backtracking, but with a constraint linking choices (open/close counts) — so it prunes, unlike this pure product.
Combination Sum
Single reusable set under a sum target → start-index template with pruning, contrasting with this fixed-position product.
Subsets
Binary in/out per element with a start index — same backtracking skeleton but one shared set and no per-position alphabet.
Permutations
Order-matters enumeration of one set with a used[] tracker — different bookkeeping, same choose/explore/un-choose core.

Same pattern

←

Palindrome Partitioning

Continue · Next problem

N-Queens

mediumBacktrackingLC #17Asked very often

Letter Combinations of a Phone Number

LCPractice

Backtracking · 6 of 13 · 9 min

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz

In plain English

Examples

Example 1

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Note: Digit 2 → {a,b,c}, digit 3 → {d,e,f}. Every pairing gives 3 × 3 = 9 combinations.

Example 2

Input: digits = ""
Output: []
Note: No digits means no combinations. Return an empty list, NOT [""].

Example 3

Input: digits = "2"
Output: ["a","b","c"]
Note: A single digit 2 yields its three letters directly.

Constraints

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

Clarifying questions4First question: What should an empty input string return?Explore questions

Q1.What should an empty input string return?
An empty list []. There are no digits, hence no letters to combine. Returning [""] (a list with one empty string) is the classic wrong answer — guard it explicitly.
Q2.Do digits 0 and 1 ever appear?
No — the constraint restricts digits to 2–9. 0 and 1 have no letters, so we never need to map them.
Q3.Does the order of the output combinations matter?
No, any order is accepted. Within each combination, order is fixed: the i-th character comes from the i-th digit.
Q4.How long can the digit string be?
At most 4 digits, so at most 4⁴ = 256 combinations. The space is tiny; the focus is on a clean product enumeration.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Returning [""] for empty input instead of [], reusing a start index (wrong model — each digit is a distinct position), or forgetting that 7 and 9 have four letters.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

The Cartesian-product recursion tree

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Backtracking over Digit Positions (Optimal)

TimeO(n · 4ⁿ)SpaceO(n)

The canonical answer. Phrase it as 'one choice-set per digit — pick a letter, recurse to the next digit, un-choose; it's a Cartesian product'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each digit maps to its own small set of letters, and a combination uses one letter from each digit in order. What familiar structure is 'one choice from each of several independent sets'?

2Hint 2Explore hint

Walk the digits left to right with an `index`. At each level, loop over the letters of `digits[index]`, append one, recurse to `index + 1`, then pop.

3Hint 3Explore hint

Record the built string when `index` reaches the end. Don't forget: if the input is empty, return [] before you even start.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

digits = "23"

Interactive diagram

Choose / explore / un-choose for "23"

index=0

Active call / nodeSupporting contextReturned stateNot active

Level 0 draws from {a,b,c}, level 1 from {d,e,f}. Every leaf is a valid combination — no branch is ever pruned.

Final result["ad","ae","af","bd","be","bf","cd","ce","cf"]

C · Code with teaching comments

solution.javaJava

Backtracking over Digit Positions (Optimal) — optimal

8 teaching notes

1
public List<String> letterCombinations(String digits) {
2
    List<String> results = new ArrayList<>();
3
    // The crucial guard — no digits means no combinations, so return [] (never [""]).
4
    if (digits == null || digits.isEmpty()) return results;   // empty input → []
5
    // Index by the digit value: indices 0 and 1 are empty placeholders so digit d maps
6
    // to map[d].
7
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
8
    backtrack(digits, 0, map, new StringBuilder(), results);
9
    return results;
10
}
11
 
12
private void backtrack(String digits, int index, String[] map,
13
                       StringBuilder path, List<String> results) {
14
    // Base case: one letter has been chosen for every digit — a complete combination.
15
    if (index == digits.length()) {
16
        // toString() materialises an immutable snapshot; later deleteCharAt won't
17
        // affect it.
18
        results.add(path.toString());          // all digits used → record built string
19
        return;
20
    }
21
    // `- '0'` converts the char digit to its int value to index the map; the alphabet
22
    // changes per position.
23
    String letters = map[digits.charAt(index) - '0'];   // this digit's alphabet
24
    for (int i = 0; i < letters.length(); i++) {
25
        // CHOOSE: commit one letter of the current digit.
26
        path.append(letters.charAt(i));                 // choose
27
        // Always advance to index+1 — every digit is used exactly once, in order.
28
        backtrack(digits, index + 1, map, path, results); // explore next digit
29
        // UN-CHOOSE: rewind the buffer so the next sibling letter starts from the same
30
        // prefix.
31
        path.deleteCharAt(path.length() - 1);           // un-choose
32
    }
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n · 4ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6digits = "" — Caught by the guard → returns [] immediately, never entering the recursion (avoids the [""] bug).Explore edge cases

Edge cases handled

digits = ""Caught by the guard → returns [] immediately, never entering the recursion (avoids the [""] bug).
digits = "79"7→pqrs (4 letters), 9→wxyz (4 letters) → 4 × 4 = 16 combinations. Confirms the 4ⁿ branching, not 3ⁿ.

Pitfalls

Returning [""] for empty input instead of [] — the #1 bug on this problem.
Forgetting the 4-letter alphabets for 7 (pqrs) and 9 (wxyz).
Using a start index as if it were one shared set — each digit is its own position with its own alphabet.
Storing a mutable buffer reference instead of a built string at the leaf.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning [""] for empty input

Explore the code comparison

Don't write this

def letterCombinations(self, digits):
    results = []
    backtrack(0, [])      # no guard → records "" and returns [""]
    return results

Write this instead

def letterCombinations(self, digits):
    if not digits:
        return []         # guard the empty input
    results = []
    backtrack(0, [])
    return results

Wrong alphabet for 7 and 9

Most digits map to 3 letters, but 7→pqrs and 9→wxyz have 4. A 3-letter-everywhere map silently drops 's' and 'z' from the output.

Explore the code comparison

Don't write this

mapping = {"7": "prs", "9": "wxy"}   # missing 's'/'z' tails!

Write this instead

mapping = {"7": "pqrs", "9": "wxyz"}  # four letters each

Using a start index instead of digit index

Explore the code comparison

Don't write this

for i in range(start, len(digits)):   # wrong model — one shared set
    for letter in mapping[digits[i]]:
        ...

Write this instead

for letter in mapping[digits[index]]: # current digit's alphabet
    path.append(letter)
    backtrack(index + 1, path)
    path.pop()

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Backtracking over a fixed sequence of choice-sets (Cartesian product)

Code pattern to memorize

def backtrack(index, path):
    if index == len(digits): results.append(''.join(path)); return
    for letter in mapping[digits[index]]:   # one choice-set per digit
        path.append(letter)                 # choose
        backtrack(index + 1, path)          # explore the next digit
        path.pop()                          # un-choose

Rules to remember

1Advance by digit index, not by a start index — every digit contributes exactly one letter, in order.
2The loop is over the current digit's letters; recursion always goes to index + 1 (never reuse the digit).
3Record only at a complete leaf (index == len(digits)) — a combination must use all digits.
4Guard the empty input: digits == "" must return [], not [""] — the most common edge-case miss.
5Use a StringBuilder/list as the path and append a built copy (toString()/''.join) at the leaf.
6Digits 7 and 9 map to 4 letters (pqrs, wxyz); the rest map to 3 — that's why the bound is 4ⁿ, not 3ⁿ.

Use this pattern when

Generate the **Cartesian product** of several independent choice-sets
Each position draws from its own fixed alphabet (digit → letters)
You need all combined strings/tuples, not just a count
The number of positions is small (digit string is short)

Choose another pattern when

Only the **count** of combinations is needed → multiply the choice-set sizes, no enumeration
Choices depend on previous picks (a constraint links positions) → it's not a plain product
The same set is reused and order doesn't matter → that's combinations/subsets, not a product
n is large → 4ⁿ explodes; full enumeration is infeasible

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Generate Parentheses
Coming soon
Also builds all strings via backtracking, but with a constraint linking choices (open/close counts) — so it prunes, unlike this pure product.
Combination Sum
Single reusable set under a sum target → start-index template with pruning, contrasting with this fixed-position product.
Subsets
Binary in/out per element with a start index — same backtracking skeleton but one shared set and no per-position alphabet.
Permutations
Order-matters enumeration of one set with a used[] tracker — different bookkeeping, same choose/explore/un-choose core.

Same pattern

←

Palindrome Partitioning

Continue · Next problem

N-Queens