Letter Combinations of a Phone Number — Solution

Problem

Given a string of digits (2–9), return all possible letter sequences those digits could represent on a phone keypad — '2' maps to "abc", '3' to "def", '7' to "pqrs", and so on. Each digit independently contributes its set of letters, and you must return every combination formed by picking exactly one letter per digit.

• Input: digits = "23"
• Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
• Explanation: '2' has 3 letters and '3' has 3 letters, yielding 3×3 = 9 two-character combinations.

If digits is "" (empty string), return [].

Intuition

Think of the problem as a decision tree: at each level you choose one letter from the current digit's set, then recurse to the next digit. The leaves of this tree are completed combinations. Backtracking explores every branch of this tree by appending a letter, going deeper, then removing the letter to try the next one — all without storing intermediate partial results.

Solution — Backtracking

Try every letter for the current digit, recurse one digit deeper with each choice, and undo the choice before moving on. The path accumulates characters level by level until it reaches length len(digits).

1. Return [] immediately if the input is empty — no digits means no combinations.
2. Build a map from each digit character to its letter string.
3. Define a recursive helper that takes the current digit index and the path built so far.
4. At the base case (index equals the number of digits), record the completed path.
5. Otherwise, loop over every letter for the current digit: append it, recurse, then pop it.
6. Kick off the recursion at index 0 with an empty path.

1def letterCombinations(digits: str) -> list[str]:
2    if not digits:
3        return []
4
5    phone_map = {
6        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
7        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
8    }
9    results = []
10
11    def backtrack(index: int, path: list[str]) -> None:
12        if index == len(digits):
13            results.append("".join(path))
14            return
15        for letter in phone_map[digits[index]]:
16            path.append(letter)
17            backtrack(index + 1, path)
18            path.pop()  # undo this choice before trying the next letter
19
20    backtrack(0, [])
21    return results

Time: O(4^n × n) — worst case 4 choices per digit (digits 7 and 9 have 4 letters), up to n digits deep, and recording each combination costs O(n) to join.
Space: O(n) — the recursion stack and the path each hold at most n elements at any point (output list not counted).

Complexity Summary

Common Mistakes

• Not guarding against empty input — if digits is "", naive backtracking would record one empty string instead of returning an empty list; the early return must come first.
• Building the path with string concatenation — passing path + letter on each recursive call creates a new string per node, adding an O(n) allocation at every step; a shared list that you join only at the base case is cleaner and faster.
• Assuming all digits map to 3 letters — digits '7' and '9' each have 4 letters (pqrs / wxyz); hardcoding a length of 3 silently drops the last letter for those digits.
• Using digit value as an array index — computing digits[i] - '0' - 2 as an array offset is error-prone; a dictionary keyed by the character itself is simpler and less likely to go out of bounds.
• Skipping the backtrack step — if you forget path.pop() (or deleteCharAt in Java), the path keeps growing across branches and produces garbage combinations like "adadad" instead of "ad".

Related Problems

• permutations — same build-and-backtrack skeleton, but choices are drawn from a shared pool that shrinks as you recurse
• subsets — at each position you decide include/exclude rather than which letter to pick
• combination-sum-ii — backtracking with skip logic to avoid duplicate branches at the same level
• palindrome-partitioning — backtracking where the choices are where to cut the string rather than which character to pick
• n-queens — backtracking with a legality check before each recursive call, illustrating pruning on top of the same tree structure