The core approach: Letter Combinations of a Phone Number is solved with backtracking in O(4^n × n) time and O(n) space. Map each digit to its letters. Recursively build combinations character by character, appending a letter for the current digit and recursing on the next. When the combination length equals the input length, add it to the result.

You’re in a coding interview. The interviewer says: “Given a string of digits 2–9, return all possible letter combinations from a phone keypad.” You’re building the Cartesian product of letter-sets — one per digit. Backtracking models this naturally.

---

Already know how to solve Letter Combinations Of A Phone Number? Try a Letter Combinations Of A Phone Number mock interview on Intervu →

The Problem

Given a string containing digits from 2-9, return all possible letter combinations. Mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz.

Example

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Backtracking structure	Do you use “build, recurse, undo” cleanly?
Base case	Do you add to results when path length equals digit count?
Empty input	Do you return [] for empty digits?

---

Step 1: The Key Insight

The problem is the Cartesian product of multiple letter-sets. At depth i, pick each letter for digits[i], recurse to i+1, and undo.

---

Python Implementation

def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []

    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    results = []
    current = []

    def backtrack(index: int) -> None:
        if index == len(digits):
            results.append(''.join(current))
            return
        for letter in phone_map[digits[index]]:
            current.append(letter)
            backtrack(index + 1)
            current.pop()

    backtrack(0)
    return results

---

Time & Space Complexity

Aspect	Complexity
Time	O(4ⁿ × n) — some keys have 4 letters
Space	O(n) — recursion stack

---

Common Interview Mistakes

1. Not handling empty input. Return [] for digits = "".
2. String concatenation instead of list. Can’t efficiently undo +=. Use list + pop().
3. Forgetting the undo step. current.pop() after recursion is essential.

---

What a Strong Candidate Sounds Like

“Backtracking over a decision tree. At each depth I choose a letter for the current digit. I maintain a path list, recurse, and pop after each call. Time is O(4ⁿ × n).”

---

Related Problems to Practice

• Subsets — Same backtracking structure.
• Combination Sum — Backtracking with target constraint.
• Permutations — Backtracking for ordered arrangements.

---

Frequently Asked Questions

What algorithm generates all possible letter combinations of a phone number?

Backtracking naturally models the combination process. By mapping the phone digits to letters, you recursively iterate through each letter choice for a given digit, passing the constructed string deeper into the call stack until hitting the length limit.

What is the time complexity to calculate the phone number combinations?

The absolute worst-case time complexity is O(4^N * N), originating from the digits 7 and 9 which contain 4 mapped letters each. Generating every branching path scales exponentially, and formatting those path strings takes linear overhead.

Practice This in a Mock Interview

Start a mock interview for Letter Combinations on Intervu.

---

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code