// Letter Combinations of a Phone Number

task

Given a string digits of digits 2-9, return every possible letter combination the number could represent, using the standard telephone keypad mapping (2 → abc, 3 → def, …, 9 → wxyz). Order doesn’t matter; an empty digits returns no combinations at all.

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

how to think

The brute force is nested loops — one per digit. That doesn’t compile as written, because the number of loops depends on digits.Length at runtime; you can’t hard-code “3 nested loops” when the input might have 2 digits or 5. Recursion is the fix: one function handles one digit position and calls itself for the rest, so “however many loops you’d need” collapses into “however many times this function calls itself.”

Each call owns exactly one digit index. It looks up that digit’s letters, and for each letter it commits the letter to the path and hands the next digit off to a recursive call. There’s no way to go wrong partway through — every letter is legal for its digit, so nothing needs pruning. That absence of pruning is what makes this the gentlest entry point into backtracking: the only two moving parts are “when do I stop” (path length equals digits.Length) and “what do I undo” (remove the last character before trying the next letter).

solution

public IList<string> LetterCombinations(string digits)
{
    if (digits.Length == 0) return [];

    string[] map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    var result = new List<string>();
    var path = new StringBuilder();

    void Backtrack(int index)
    {
        if (index == digits.Length)
        {
            result.Add(path.ToString());
            return;
        }

        foreach (char c in map[digits[index] - '0'])
        {
            path.Append(c);           // choose
            Backtrack(index + 1);     // explore
            path.Length--;            // un-choose
        }
    }

    Backtrack(0);
    return result;
}

trace

digits = "23" — '2' maps to "abc", '3' maps to "def":

""
├─ 'a' → "a"
│    ├─ 'd' → "ad"   (index 2 == digits.Length → ADD)
│    ├─ 'e' → "ae"   (ADD)
│    └─ 'f' → "af"   (ADD)
├─ 'b' → "b"
│    ├─ 'd' → "bd"   (ADD)
│    ├─ 'e' → "be"   (ADD)
│    └─ 'f' → "bf"   (ADD)
└─ 'c' → "c"
     ├─ 'd' → "cd"   (ADD)
     ├─ 'e' → "ce"   (ADD)
     └─ 'f' → "cf"   (ADD)

Every choose event in that tree, in the order the recursion actually visits them:

Every one of the 12 rows is a real call to Backtrack; after each add, path.Length-- fires before the loop tries the next letter — that’s why row 5 starts from "b" and not "ab".

why it works

Every path from the root to a leaf of depth digits.Length picks exactly one letter per digit, and every combination of “one letter per digit” is reachable by exactly one such path — the recursion tree’s leaves are in one-to-one correspondence with the answer set. StringBuilder makes the choose/un-choose pair O(1): Append commits a letter, path.Length-- removes it without reallocating, so undoing is as cheap as choosing.

common bugs

• Returning [""] instead of [] when digits is empty — LeetCode wants an empty list, and the guard if (digits.Length == 0) return []; has to be explicit; without it the recursion starts at index == 0 == digits.Length and immediately adds one empty string.
• Using path += c (string concatenation) instead of a mutable StringBuilder — strings are immutable, so there’s no O(1) undo; you’d have to slice the string back down, which works but throws away the whole point of choose/un-choose being cheap.
• Indexing the map with the raw character — map[digits[index]] instead of map[digits[index] - '0'] — throws IndexOutOfRangeException, since digits[index] implicitly converts to an int in the 50s (its ASCII value), and map only has 10 elements.
• Forgetting path.Length-- after the recursive call: leftover characters from one branch bleed into the next sibling, and every combination after the first gets longer than it should.

variants you can now solve

• Subsets (LC 78) — the next rung up: instead of a fixed choice per position, every element gets a binary include/skip decision.
• Permutations (LC 46) — the choice list isn’t a fixed per-digit lookup anymore; it’s “whatever’s still unused,” so it shrinks every level.
• Combinations (LC 77) — pick k numbers from 1..n; same fixed-depth shape as this problem, but the “digit map” becomes a shrinking numeric range instead of a keypad lookup.