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.

---

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"]

Already comfortable with the solution? Practice it in a mock interview →

---

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.

---

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