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.
How GhostInterview Helps
- Capture and screenshot input digits and the corresponding phone mapping to ensure accurate test cases for the session.
- Provide step-by-step answer paths with complexity explanation, highlighting recursive backtracking decisions and pruning rationale.
- Support screen-share workflows by visually displaying captured recursion layers and queue expansions for easier interviewer walkthroughs.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Letter Combinations of a Phone Number instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Letter Combinations of a Phone Number from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find all shortest transformation sequences from beginWord to endWord using a dictionary, leveraging backtracking search with pruning for efficiency.
Open problem page#140 Word Break IIGiven a string and dictionary, return all possible sentences by adding spaces where each word is in the dictionary.
Open problem page#691 Stickers to Spell WordDetermine the minimum number of stickers needed to spell a target word using array scanning and hash lookups for efficient letter tracking.
Open problem page