Letter Combinations of a Phone Number

BACKTRACKING · MEDIUM

Builds on Day 9: Recursion & the Call Stack

Solution 2 below is a direct application of recursive backtracking; read that lesson first if the call-stack mental model is still new.

The problem

Given a string digits containing digits 2-9, return all possible letter combinations that the number could represent, based on the standard telephone keypad mapping (2 = abc, 3 = def, 4 = ghi, 5 = jkl, 6 = mno, 7 = pqrs, 8 = tuv, 9 = wxyz). Return the answer in any order.

Solution 1: Iterative — expand the combos list one digit at a time

Start with a list containing just the empty string. For each digit in turn, cross the current list against that digit’s letters, producing a new, longer list — no recursion needed at all.

Flow diagram

Iterative: expand the combos list one digit at a time
    ↓
combos = [""]  →  for each digit's letters  →  combos grows
(start empty)      (cross with existing combos)  (no recursion at all)

Cost: O(4^n) worst case — same as the backtracking version below.

Interactive visualization

digits = "23" — mapping: 2 = abc, 3 = def

Press play to expand the combos list.

Step 0 / 3

▶ Play↺ Reset

This animation traces digits=“23” — a small case verified above.

The code

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

function letterCombinationsIterative(digits) {
  if (digits.length === 0) return [];
  let combos = [''];
  for (const d of digits) {
    const letters = PHONE[d];
    const next = [];
    for (const combo of combos) for (const letter of letters) next.push(combo + letter);
    combos = next;
  }
  return combos;
}

Line by line:

• combos starts as [''] — one empty combination, ready to be extended.
• For each digit, a fresh next array is built by combining every existing combo with every letter that digit maps to — this is what makes combos grow by a factor of 3 or 4 with each digit processed.
• digits.length === 0 returns [] immediately — there’s nothing to expand, and the problem defines the empty-input answer as an empty list, not a list containing one empty string.

Complexity

Time	Space
O(4^n) worst case	O(4^n) to store all combinations

Solution 2: Backtracking — recurse one digit at a time

This does exactly the same total work as the iterative version above — it’s just structured as recursion instead of a loop. At each recursive call, pick one letter for the current digit, and recurse to the next digit. This is a different technique, not a faster one.

Flow diagram

Backtracking: recurse one digit at a time (same complexity, different technique)
    ↓
pick a letter  →  recurse to index+1  →  full length reached
(for digits[index]) (next digit)       (record the combination)

Cost: O(4^n) worst case — same asymptotic class as the iterative version above.

Interactive visualization

digits = "23" — recursion call stack animation

Press play to trace the recursive backtracking.

Step 0 / 35

▶ Play↺ Reset

This animation traces digits=“23” — the same small case verified above.

The code

function letterCombinationsBacktrack(digits) {
  if (digits.length === 0) return [];
  const result = [];
  function dfs(index, path) {
    if (index === digits.length) { result.push(path); return; }
    const letters = PHONE[digits[index]];
    for (const letter of letters) dfs(index + 1, path + letter);
  }
  dfs(0, '');
  return result;
}

Line by line:

• index tracks which digit of the input is currently being expanded — it also doubles as the recursion’s stopping condition once it reaches digits.length.
• path + letter builds the combination string incrementally as the recursion goes deeper — strings are immutable in JavaScript, so this always creates a new string rather than mutating one, unlike the array-based path.push/path.pop pattern used elsewhere in this batch.
• The base case (index === digits.length) means every digit has been assigned a letter — path is now a complete combination.

Complexity

Time	Space
O(4^n) worst case	O(n) recursion depth (plus O(4^n) for the output)

Complexity comparison

Solution	Time	Technique
Iterative (list expansion)	O(4^n)	Loop-based, builds a growing list
Backtracking (recursion)	O(4^n)	Recursion-based, builds one string at a time

Unlike every other problem in this batch, there’s no naive-vs-optimized story here — the output size (up to 4^n combinations) sets an unavoidable lower bound on the work, so neither technique can beat the other asymptotically. This page is here to show that the SAME problem can be solved with genuinely different, equally valid approaches — knowing both means you’re not locked into recursion as the only tool for combinatorial generation.

Interview corner

Why does this problem not have a meaningful “brute force vs. optimal” complexity gap, unlike most other backtracking problems in this batch?

• The output itself is unavoidably exponential — there’s no way to produce fewer results than the problem actually has, so no algorithm can beat that lower bound.
• Both solutions shown are genuinely different techniques (iterative expansion vs. recursive backtracking) at the same complexity class, not a naive-vs-smart pair.

How would you modify the backtracking solution to return combinations sorted by length first, then alphabetically?

• Every combination produced here already has the same fixed length (digits.length), so plain alphabetical order — which both solutions already produce, since each digit’s letters are listed alphabetically in the PHONE mapping — already satisfies that request.
• Length-based sorting only matters when combinations can have different lengths, which isn’t the case here.

What if a digit like ‘1’ or ‘0’ (which map to no letters on a real phone keypad) appears in the input?

• Neither solution shown handles it — PHONE[digit] would be undefined, and iterating over undefined’s “letters” would throw a runtime error.
• Worth explicitly asking the interviewer whether the input is guaranteed to only contain digits 2-9, which is what LeetCode’s actual problem constraints state.

Trick question — what does this log?

console.log("10" > "9");

• Answer: false.
• String comparison in JavaScript is lexicographic — character by character, left to right — not numeric.
• '1' (char code 49) is less than '9' (char code 57), so "10" is considered “less than” "9" as strings, even though 10 > 9 as numbers.
• ⚠ Trap: this is directly relevant here because digits in this problem IS a string of digit characters — comparing or sorting digit strings without first converting them to numbers can silently produce wrong results.

Quiz

Quiz: 1. Why does an empty digits string return an empty array, not an array containing an empty string?

Both solutions special-case this — the iterative version has no digits to expand the initial [""] against, and the backtracking version explicitly returns early instead of ever calling dfs

Both solutions special-case this — the iterative version has no digits to expand the initial [""] against, and the backtracking version explicitly returns early instead of ever calling dfs.

Quiz: 2. What does the iterative solution’s inner double loop do at each digit?

For every existing partial combination so far, it appends each possible letter for the current digit, expanding the combos list by a factor of however many letters that digit maps to

For every existing partial combination so far, the inner loop appends each possible letter for the current digit, expanding the combos list by a factor of however many letters that digit maps to.

Quiz: 3. Why do the iterative and backtracking solutions have the same time complexity despite looking very different?

Both must ultimately construct every one of the possible combinations — the total output size sets the same lower bound either way

Both must ultimately construct every one of the possible combinations — the total output size sets the same lower bound either way, regardless of whether a loop or recursion is used to build it.

Quiz: 4. In the backtracking version, what does the index parameter track?

Which digit of the input string is currently being expanded — it also doubles as the recursion’s stopping condition once it reaches digits.length

index tracks which digit of the input string is currently being expanded, and it also doubles as the recursion’s stopping condition once it reaches digits.length.

Quiz: 5. Which solution would need real changes to also return combinations sorted alphabetically, and why?

Neither — since each digit’s letters are already listed alphabetically, both solutions naturally produce combinations in alphabetical order already

Neither needs changes — since each digit’s letters are already listed alphabetically in the PHONE mapping, both solutions naturally produce combinations in alphabetical order already.