Letter Combinations of a Phone Number

1. Problem & Core Objective

Given a string of digits 2–9, return all letter combinations the number could spell, using the classic phone keypad.

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

digits = "23"
→ ["ad","ae","af","bd","be","bf","cd","ce","cf"]      3 × 3 = 9

digits = ""
→ []

Constraints: 0 <= digits.length <= 4 · digits are 2–9 only

What's actually being tested: the simplest possible backtracking — no constraints at all, so nothing is ever pruned. It's a Cartesian product, and the only real trap is the empty input. It's here to show the template working when the "choices" come from a lookup rather than the input itself.

2. First-Principles Thought Process

It's a Cartesian product

Each digit contributes one letter, chosen independently from that digit's set. So the answer count is the product of the set sizes:

"23"   → 3 × 3 = 9
"234"  → 3 × 3 × 3 = 27
"7979" → 4 × 4 × 4 × 4 = 256      ← the maximum, since 7 and 9 have four letters

With digits.length <= 4 the output is at most 256 combinations — tiny.

The structure

Position i in the digit string is one level of the recursion. The choices at that level are the letters mapped to digits[i].

for (char letter : LETTERS[digit]) {
    path.append(letter);
    backtrack(i + 1);
    path.deleteCharAt(path.length() - 1);
}

Identical to every previous question. The only difference is where the choices come from — a lookup table rather than the input array.

Nothing is pruned

Every combination is valid. There's no constraint, no validity check, no early break. That makes this the cleanest demonstration that backtracking is just structured enumeration — the pruning is an optional addition, not part of the definition.

The one real trap

digits = "" must return [], not [""].

Without a guard, the recursion immediately hits its base case with an empty path and records the empty string — one result where there should be zero. It's a single if, and it's the only thing that can go wrong here.

3. Solution Paths

Approach 1 — Iterative Cartesian product

public List<String> letterCombinations(String digits) {
    if (digits.isEmpty()) return new ArrayList<>();

    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    result.add("");                                     // seed with one empty combination

    for (char d : digits.toCharArray()) {
        List<String> next = new ArrayList<>();
        for (String prefix : result)
            for (char letter : map[d - '0'].toCharArray())
                next.add(prefix + letter);
        result = next;
    }
    return result;
}

Each digit multiplies the result set by that digit's letter count.

• Time O(L · 4^L) where L = digits.length · Space O(4^L)

Counter-questions on this approach

⭐ "Why seed with "" rather than an empty list?"

Because the loop extends existing prefixes. Starting from an empty list, the inner loop has nothing to iterate over and the result stays empty forever.

The empty string is the identity for concatenation — it's the single "combination of zero digits" that everything builds from. Same role as result.add(new ArrayList<>()) in the iterative Subsets approach.

⭐ "Why the early return for empty input, given the seed is \"\"?"

Because without it, the loop never runs and the function returns [""] — a list containing the empty string. The problem wants [], a list of nothing.

That's the distinction: one combination of zero letters versus no combinations at all. It's the only edge case in this problem, and the only thing an otherwise-correct solution gets wrong.

"Is the string concatenation a problem?"

prefix + letter allocates a new string each time — O(L) per combination, so O(L · 4^L) overall. At L = 4 that's 256 short strings, irrelevant.

The backtracking version uses a single StringBuilder and only materialises a string at the leaves, which is asymptotically the same but allocates far less.

Approach 2 — Backtracking (the template)

private static final String[] LETTERS =
    {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits.isEmpty()) return result;               // [] not [""]
    backtrack(digits, 0, new StringBuilder(), result);
    return result;
}

private void backtrack(String digits, int i, StringBuilder path, List<String> result) {
    if (i == digits.length()) {                        // one letter per digit — complete
        result.add(path.toString());
        return;
    }

    for (char letter : LETTERS[digits.charAt(i) - '0'].toCharArray()) {
        path.append(letter);                           // choose
        backtrack(digits, i + 1, path, result);        // explore
        path.deleteCharAt(path.length() - 1);          // un-choose
    }
}

Trace — digits = "23":

9 combinations ✓

• Time O(L · 4^L) · Space O(L) for the path and the stack

Counter-questions on this approach

⭐ "There's no pruning anywhere. Is this still backtracking?"

Yes — backtracking is choose/explore/un-choose. Pruning is an optional addition that some problems permit and others don't.

Here every combination is valid, so there's nothing to cut. That makes this the cleanest illustration that the skeleton is fundamentally structured enumeration; pruning is what makes it efficient on constrained problems, not what makes it backtracking.

⭐ "Why StringBuilder rather than string concatenation?"

Java strings are immutable, so path + letter allocates a new string at every node — O(L) each. A StringBuilder appends in amortized O(1) and I only pay toString() at the leaves, where I genuinely need a string.

It also makes the un-choose natural: deleteCharAt(length - 1) is the mutable-state removal that matches path.remove(...) in the list versions.

⭐ "What exactly does the empty-input guard prevent?"

Without it, backtrack("", 0, ...) immediately satisfies i == digits.length() (both zero) and records "". The result is [""] — one combination — when it should be [].

It's the only edge case in the problem, and it's a semantic distinction rather than a crash: "one empty combination" versus "no combinations".

"Why does LETTERS have two empty entries at the start?"

So the digit character maps directly to an index: LETTERS[digits.charAt(i) - '0'] gives index 2 for '2'. The entries for 0 and 1 are placeholders that can never be indexed, since the constraint restricts digits to 2–9.

A Map<Character, String> would avoid them but adds a hash lookup per node for no benefit with a dense, tiny key range.

"Could the recursion be deeper than 4?"

No — depth equals digits.length(), capped at 4. So the stack is trivially bounded, and the whole search is at most 256 leaves.

"Does output order matter?"

The problem says any order. This produces them in lexicographic order of the keypad letters, which happens to match the expected output in the examples — but that's incidental, not required.

Comparison

4. Why the Optimal Wins

Both are O(L · 4^L), which is optimal — the output is that size.

The backtracking version holds O(L) state instead of O(4^L): one path being mutated, rather than every intermediate level materialised. And it allocates a string only at each leaf rather than at every prefix extension.

At L = 4 neither matters. The reason to write it is that it's the same template as everything else in this section, and the iterative version — like the iterative variants in Subsets and Permutations — has nowhere to put a constraint if one appeared.

The framing worth keeping:

Backtracking with no pruning is just structured enumeration of a Cartesian product. The choices don't have to come from the input — here they come from a lookup table.

5. Java Prerequisites

Digit-to-letters lookup

private static final String[] LETTERS =
    {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
LETTERS[digits.charAt(i) - '0']      // '2' -> index 2

StringBuilder as the mutable path

path.append(letter);
path.deleteCharAt(path.length() - 1);   // the un-choose
path.toString();                         // materialise only at a leaf

String.toCharArray() to iterate characters; charAt(i) avoids the copy if you prefer an index loop.

Empty input — return an empty list before recursing, or you get [""].

6. Interview Communication Guide

Clarifying questions: What should empty input return ([], not [""] — this is the only trap)? Can digits include 0 or 1 (no — 2–9 only)? Does output order matter (no)? Maximum length (4, so at most 256 results)?

The pitch

"This is a Cartesian product — each digit independently contributes one letter, so the answer count is the product of the letter-set sizes. With at most four digits and four letters each, that's at most 256 combinations.

The backtracking is the same template as everything else: position i in the digit string is one level, and the choices at that level are the letters mapped to that digit. Append, recurse, remove.

The one thing worth noting is that nothing is ever pruned — every combination is valid, so there's no validity check and no early exit. That's actually useful to say out loud: it shows backtracking is fundamentally structured enumeration, and pruning is an optional addition for constrained problems rather than part of the definition.

I use a StringBuilder for the path rather than string concatenation, since Java strings are immutable and path + letter would allocate at every node. The deleteCharAt is the un-choose.

The only real edge case is empty input, which must return [] rather than [""]. Without a guard, the recursion immediately hits its base case with an empty path and records the empty string — one combination where there should be zero. It's a semantic distinction rather than a crash, so it passes casual testing.

O(L · 4^L) time, which is the output size, and O(L) space."

Edge cases to volunteer:

Name the empty input. It's the only case an otherwise-correct solution gets wrong, and [""] versus [] is easy to overlook because both look "empty" at a glance.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the digit string could be 10 digits long?"

4^10 is about a million combinations, each 10 characters — roughly 20 MB of output. Still materialisable, but at 15 digits it's a billion. You'd switch to streaming: yield each combination through a callback or Iterator rather than accumulating a list. The backtracking structure supports that naturally; the iterative product does not, since it holds every level.

⭐ "Filter to combinations that are real words."

Now there is something to prune. With a trie of the dictionary, you walk it in lockstep with the digits and abandon a branch the moment no word has that prefix — exactly the Word Search II idea. That turns an unpruned enumeration into a heavily pruned search, and is the classic T9 predictive-text algorithm.

"Include digits 0 and 1, which map to no letters."

Their letter sets are empty, so the loop body never runs and that branch produces nothing — meaning the whole result becomes empty, since every digit must contribute a letter. Worth deciding deliberately whether they should be skipped instead, which is a spec question.

"Return the count without listing them."

Multiply the set sizes — O(L) with no search at all. Another instance of counting being trivially cheaper than enumerating.

"Generate the k-th combination directly."

Mixed-radix decomposition: divide k by the later digits' sizes to pick each letter, exactly like the factorial number system for permutations. O(L), no enumeration. The ordering is a numbering.

"What if each digit's letters came from a runtime configuration?"

Nothing structural changes — replace the constant table with the supplied map. The template never depended on the choices being fixed, which is the point of separating "where choices come from" out of the skeleton.