Letter Combinations of a Phone Number

Problem Given a string of digits 2–9, return all possible letter combinations the number could represent on a telephone keypad, in any order.

Input / Output

• Input: string digits.
• Output: list of all letter combinations (empty list for empty input).

Constraints

• 0 <= |digits| <= 4 in the classic setting; output size is up to 4^n — exponential by nature.

Example

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

Expected approach

• Backtracking: map each digit to its letters, build combinations depth-first, appending one letter per digit and backtracking. O(4^n * n) time. An iterative BFS (extend all partials digit by digit) is equivalent — mention both and why recursion depth is bounded by |digits|.