Standard Bar Recursion · Subsequences Pattern O(4^n * n) worst case — up to 4 letters per digit, n to copy each string · O(n) recursion depth beyond the output
A call center reserves vanity extensions typed as digit strings, and the switchboard must publish every word each digit sequence could spell under the classic keypad mapping (2 = ABC, 3 = DEF, and so on; 7 and 9 carry four letters). The operator types one digit at a time, branching over that key's letters, and the catalogue is complete when the last digit's options are exhausted.
Input: A string digits containing only characters '2'-'9'.
Output: Every letter combination, in the order the depth-first walk produces them; an empty input yields an empty list.
0 <= digits.length <= 4digits[i] is a digit in the range ['2', '9']Input: {"digits":"23"}
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Three letters for '2' times three for '3', crossed in keypad order.
Input: {"digits":"2"}
Output: ["a","b","c"]
A single digit simply lists its own letters.