Letter Combinations of a Phone Number

Problem

Autocomplete systems on phones map digit sequences to candidate words by enumerating all letter combinations the digits could spell. Given a string of digits (2-9), return all possible letter combinations they could represent using the standard telephone keypad mapping. Return an empty list for empty input.

Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
 
Input: ""
Output: []
 
Input: "2"
Output: ["a","b","c"]

Solution

Approach: Backtracking where each recursion depth resolves exactly one digit.

Unlike subset or permutation generation, the loop here is not over an index range - it is over the letters mapped to the current digit. The recursion carries a single index into digits; at depth d the loop iterates phone_map[digits[index]], the letters for that one digit. For each letter it does choose-explore-unchoose: path.append(char), recurse with index + 1 to resolve the next digit, then path.pop(). The base case fires when index == len(digits) - the path now holds one character per digit, so "".join(path) is a complete combination and gets recorded. The tree's depth equals the number of digits, and each node fans out by the size of its digit's letter set (3 for most, 4 for 7 and 9). Trace "23": the root loops a, b, c for digit 2; under a it loops d, e, f for digit 3, emitting ad, ae, af; backtracking to b and c yields the remaining six - 9 strings total. The explicit empty-input guard if not digits: return [] is required, otherwise backtrack(0) would join an empty path and wrongly return [""].

Edge cases: Empty input returns [] (not [""]) thanks to the guard. A single digit produces one string per mapped letter.

Complexity: O(4^n * n) time, O(n) space - up to 4^n leaves (digits 7/9), each joined in O(n); recursion depth and path are bounded by the digit count n (output excluded).