A support search index expanded old T9 sequences so a typed 43556 could match hello. The intern nested two loops because the first ticket was always two digits: every letter on the first key times every letter on the second. Staging with "23" returned nine strings before coffee. Then marketing shipped four-digit campaign codes and there was no third loop in the file.

Letter Combinations of a Phone Number asks for every string a digit sequence could type on a phone keypad. Digit 2 opens abc, 7 opens pqrs. Nested loops use that mapping and still freeze the length at compile time.

This is an interview writeup, not a backtracking lecture. The backtracking post owns choose, recurse, and undo. Here we only care about the keypad mapping so each digit opens a letter bucket, and the path holds one letter per digit.

The problem

Given a string digits whose characters are '2' through '9', return all letter combinations the number could represent. The mapping is the classic phone keypad. Order does not matter. Empty digits returns an empty list.

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"]
digits = "2"   →  ["a","b","c"]
digits = ""    →  []

Note: Growing a list of prefixes — cartesian product, one digit at a time — is a legal middle path. It is not the usual interview answer: you still allocate every prefix list. A shared path walks the same tree and undoes.

Nested loops freeze the length

Two digits: two loops over the two buckets. Correct for "23". A third digit needs a third loop. The compiler will not write it for you.

List<String> letterCombinationsNested(String digits) {
    String[] map = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    List<String> out = new ArrayList<>();
    String a = map[digits.charAt(0) - '0'];
    String b = map[digits.charAt(1) - '0'];
    for (int i = 0; i < a.length(); i++) {
        for (int j = 0; j < b.length(); j++) {
            out.add("" + a.charAt(i) + b.charAt(j));
        }
    }
    return out;
}

At two digits this is a rounding error. At a variable n you paid a nest that does not exist: which letter does this digit still allow?

One path: append a letter, recurse, undo

Index i is the digit you are filling. A ten-slot array makes map[d - '0'] the bucket (7 is four letters, not three). For each letter: append it, recurse to i + 1, then delete the last character. When i equals digits.length(), record path.toString(). Empty input never enters the walk.

Walk "23":

digits = "23"   map 2→abc  3→def
path = ""

i=0  digit 2
  append a  path="a"
    i=1  digit 3
      append d  path="ad"  i=2 → record "ad"; delete d
      append e  path="ae"  record "ae"; delete e
      append f  path="af"  record "af"; delete f
    delete a  path=""
  append b  → "bd","be","bf"; delete b
  append c  → "cd","ce","cf"; delete c

The Java is that walk:

List<String> letterCombinations(String digits) {
    List<String> out = new ArrayList<>();
    if (digits.isEmpty()) {
        return out;
    }
    String[] map = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    backtrack(digits, 0, new StringBuilder(), map, out);
    return out;
}

void backtrack(String digits, int i, StringBuilder path,
               String[] map, List<String> out) {
    if (i == digits.length()) {
        out.add(path.toString());
        return;
    }
    String letters = map[digits.charAt(i) - '0'];
    for (int k = 0; k < letters.length(); k++) {
        path.append(letters.charAt(k));
        backtrack(digits, i + 1, path, map, out);
        path.deleteCharAt(path.length() - 1);
    }
}

Time is O(4^n · n) — digits 7 and 9 have four letters, and each leaf copies a path of length n. Extra space is O(n) for the path and the call stack, not counting the output list.

Note: Empty digits return [], not [""]. Skip the empty check, start at i = 0, and i == digits.length() is already true — you record one empty combination. The early return is correctness.

What interviewers usually poke next

  • Cartesian product / a queue of prefixes. Same mapping, no shared path: each digit replaces every current prefix with prefix + letter. Correct, and it allocates a new list per digit. Say why the undo is the default when they asked for the tree.
  • Digits 0 and 1. The classic keypad has no letters there. An empty bucket produces no children, so the result is empty if any digit maps to "". This prompt’s range is 2–9; ask before you invent those slots.
  • Why StringBuilder, not path + c. Concatenation is a new string per choice. Append and deleteCharAt mutate one buffer. Either is accepted if you can name the copy cost at the leaf.
  • n is tiny. LeetCode caps length at four, so 4^4 is a rounding error. Nested loops still freeze that four. The answer they want is the mapping plus a path whose length is not a nest of fors.

You are done with this problem when you can say, out loud, why two nested loops are correct for "23", why the map is a keypad bucket and not a second undo lecture, and why empty input is [] rather than [""].