Letter Combinations of a Phone Number

Valid Parentheses

Roman to Integer

Generate every letter combination represented by digits on a telephone keypad.

Given a string of digits from `2` through `9`, return every possible letter combination using the traditional telephone keypad mapping. Preserve digit order and emit combinations in keypad order. Return an empty list for an empty input.

**Input / output**
- Input: `digits: string`
- Output: `string[]`

**Examples**
1. `"23"` returns `["ad","ae","af","bd","be","bf","cd","ce","cf"]`.
2. `""` returns `[]`.

**Constraints**
- `0 <= digits.length <= 4`
- Every character is between `2` and `9`.

**Follow-up**
What are the time and output-space bounds when digits `7` and `9` contribute four choices?

- Each digit maps to a small group of letters, like `2 -> abc` and `3 -> def`.
- A valid answer chooses exactly one letter for every digit.
- If `digits` is empty, there are no combinations to build, so return an empty list.

Understand the Search Space

- Keep a list of partial combinations seen so far.
- For the next digit, append each possible letter to each partial combination.
- This works, but recursion or backtracking expresses the choice process more directly.

Start with Incremental Building

- Backtracking builds one candidate combination at a time.
- At position `i`, choose one letter for `digits[i]`, recurse to the next position, then try the next letter.
- When the candidate length equals the input length, it is complete.

Use Backtracking

- Iterate through digits from left to right.
- Iterate through each mapped letter in the normal phone keypad order.
- This naturally produces results like `ad, ae, af, bd, ...` for `23`.

Preserve the Required Order

- The final solution handles the empty input first, then backtracks through every possible letter choice.
- If there are `n` digits and each has up to 4 letters, time complexity is O(4^n * n) including string creation.
- Space complexity is O(n) for the recursion path, plus the output list.