Letter Combinations of a Phone Number

Start with a backtracking approach that explores each digit's mapped letters recursively while pruning impossible paths early. Construct partial combinations step by step, appending each valid letter and backtracking once all options for a position are explored. This guarantees that all valid letter sequences are generated efficiently without redundant computation.

Problem Statement

Given a string of digits from 2 to 9 inclusive, return all possible letter combinations the number could represent. Each digit maps to letters like a telephone keypad, and the solution must generate every valid sequence without skipping any combination. Return the combinations in any order. Empty input should return an empty list, and each combination should preserve the order of digits in the input string.

You are provided a mapping from digits to letters: 2 → 'abc', 3 → 'def', 4 → 'ghi', 5 → 'jkl', 6 → 'mno', 7 → 'pqrs', 8 → 'tuv', 9 → 'wxyz'. The problem requires a backtracking approach that tries all letters for each digit recursively while avoiding paths that cannot yield valid results. Constraints include a maximum input length of 4 digits, each between 2 and 9, ensuring solutions remain tractable with pruning.

Examples

Example 1

Input: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example details omitted.

Example 2

Input: digits = ""

Output: []

Example details omitted.

Example 3

Input: digits = "2"

Output: ["a","b","c"]

Example details omitted.

Constraints

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Solution Approach

Recursive Backtracking

Implement a recursive function that tracks the current combination and the index in the digit string. For each digit, loop over its corresponding letters from the hash table and append each letter to the combination. Recursively call the function for the next index, and backtrack by removing the last letter after each call. This approach ensures that all possible sequences are generated without storing unnecessary intermediate states, keeping recursion depth limited to the input length.

Iterative Backtracking with Queue

Use a queue to store partial combinations and iteratively extend them with letters from the current digit. For each partial combination in the queue, append every possible letter of the next digit and enqueue the result. Repeat until all digits are processed. This method avoids deep recursion, provides clear breadth-first generation, and naturally prunes combinations that cannot be completed, offering a controlled alternative to standard recursive backtracking.

Pruning Invalid Paths

At each recursion or iteration step, check if the current partial combination length exceeds the number of digits; if so, stop exploring that path. Early termination prevents unnecessary recursive calls or queue expansions, significantly improving efficiency for longer digit strings. This pruning ensures memory and CPU usage remain proportional to valid combinations, which is critical given the exponential growth of possibilities with each additional digit.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(4^n * n), where n is the number of digits, because each digit can map up to 4 letters and each combination requires string construction. Space complexity is O(n) for the recursion stack or queue storage. These complexities directly reflect the backtracking search and pruning process used to generate all valid combinations efficiently.

What Interviewers Usually Probe

• Do you handle empty input correctly to avoid unnecessary recursion?
• Can you explain how pruning prevents generating invalid or partial combinations?
• Will you optimize the combination construction to avoid redundant string copies?

Common Pitfalls or Variants

Common pitfalls

• Failing to prune paths when the current combination exceeds the input length, leading to unnecessary recursion.
• Ignoring edge cases like empty input or single-digit input, which require returning empty or single-letter combinations.
• Constructing new strings at every recursion step without backtracking, which increases memory usage and slows performance.

Follow-up variants

• Return letter combinations only for digits that map to exactly three letters, skipping digits like 7 and 9 with four letters.
• Count the total number of valid letter combinations without returning the sequences themselves, focusing on performance optimization.
• Generate combinations in lexicographical order rather than any order, adding a sorting constraint after backtracking.

FAQ

How does backtracking apply to Letter Combinations of a Phone Number?

Backtracking allows the algorithm to explore every letter for each digit recursively, building partial combinations and pruning paths that cannot form valid sequences.

What is the maximum number of combinations for a 4-digit input?

The maximum is 4^4 = 256 combinations, considering digits like 7 or 9 which map to four letters, and this must be handled efficiently by pruning.

Can the output order be arbitrary?

Yes, the problem allows any order for the combinations, although a lexicographical order variant exists if sorting is needed after generation.

What should the function return for an empty string input?

An empty input string should return an empty list since there are no digits to map to letters, which avoids unnecessary recursion.

How do I optimize memory usage during backtracking?

Use in-place modification of a single combination buffer and backtrack by removing the last appended letter, instead of creating new strings at each recursion level.