Letter Combinations of a Phone Number

On a phone keypad, the digits 2 through 9 each stand for a few letters:

Digit	Letters	Digit	Letters
2	abc	6	mno
3	def	7	pqrs
4	ghi	8	tuv
5	jkl	9	wxyz

Given a string digits made of the characters 2–9, return every string you can make by choosing one letter for each digit, keeping the digits in order.

Return the strings in any order. If digits is empty, return an empty list.

"Return every combination" is the signal for backtracking. Each digit is a decision with a few options, and the decisions are independent, so the answers are the leaves of a tree: the root is the empty string, each level adds one letter for the next digit, and the depth equals len(digits).

You can't do this with a fixed number of nested loops because the number of digits varies. Recursion gives you exactly one "loop" per digit: at position i, try each letter for digits[i], recurse on i + 1, then undo the choice. When i reaches the end, the current path is a complete answer.

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


def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []
    results = []
    path = []

    def backtrack(i: int) -> None:
        if i == len(digits):
            results.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return results

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

function letterCombinations(digits) {
  if (!digits) return [];
  const results = [];
  const path = [];

  const backtrack = (i) => {
    if (i === digits.length) {
      results.push(path.join(''));
      return;
    }
    for (const letter of KEYPAD[digits[i]]) {
      path.push(letter);
      backtrack(i + 1);
      path.pop();
    }
  };

  backtrack(0);
  return results;
}

Describe the decision tree before you code: one level per digit, one branch per letter, answers at the leaves. That framing tells the interviewer you can recognize backtracking, and it gives you the complexity for free: up to 4 branches per level and n levels, with O(n) work to build each leaf.

Handle the empty input first and say so out loud. Then write the choose / recurse / undo structure clearly, because it's the template for harder problems like permutations, subsets and N-Queens.