DSA Tracker

Visualize

Letter Combinations of a Phone Number

Depth-first search over telephone keypad mappings

time O(4^n * n)space O(n)

Each digit on a phone keypad maps to a discrete set of letters (2="abc", 3="def"). Generating all combinations is a depth-first tree traversal where depth corresponds to digit index. At depth i, iterate through every letter mapped to digits[i], append it to the current path, recurse to depth i+1, and pop the letter (backtrack) upon return. When depth reaches the length of digits, the path forms a complete combination.

Details

Animated on: digits = "23" — return all possible letter combinations that the numbers could represent (2 maps to "abc", 3 maps to "def").

Problem:Letter Combinations of a Phone NumberMedium

Pattern:Backtracking with Constraints

Depth-first search over telephone keypad mappings

step 1 / 12

a
[0]

idx=0 (digit '2' → 'abc'): choose letter 'a'. path = ['a']. Recurse to idx=1.

  • idx:0=0· arr[0] = a
Pseudocode
1FUNCTION letterCombinations(digits):
2  IF digits is empty: RETURN empty list
3  phone = a table mapping each digit to its letters ('2'->'abc', '3'->'def')
4  ans = empty list of results, path = empty current combination
5  FUNCTION backtrack(idx):
6    IF idx equals the length of digits: join path into a string and add it to ans; RETURN
7    FOR each letter mapped to digits[idx]:
8      add letter to path; backtrack(idx + 1); remove the last letter from path
9    END FOR
10  backtrack(0); RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. idx=0 (digit '2' → 'abc'): choose letter 'a'. path = ['a']. Recurse to idx=1.
  2. idx=1 (digit '3' → 'def'): choose 'd'. path = ['a', 'd']. Leaf reached! Record 'ad'. ans=['ad'].
  3. Backtrack: pop 'd', push 'e'. path = ['a', 'e']. Leaf reached! Record 'ae'. ans=['ad', 'ae'].
  4. Backtrack: pop 'e', push 'f'. path = ['a', 'f']. Leaf reached! Record 'af'. ans=['ad', 'ae', 'af'].
  5. Backtrack to idx=0: digit 2 advances to next choice 'b'. path = ['b']. Recurse to idx=1.
  6. At idx=1: choose 'd' → 'bd'. Backtrack and try 'e' → 'be', then 'f' → 'bf'. ans now has 6 combinations.
  7. Branch for 'b' completes with 'bf'. ans=['ad', 'ae', 'af', 'bd', 'be', 'bf'].
  8. Backtrack to idx=0: digit 2 advances to final choice 'c'. path = ['c']. Recurse to idx=1.
  9. At idx=1: choose 'd' → path=['c', 'd']. Leaf! Record 'cd'.
  10. Backtrack and choose 'e' → path=['c', 'e']. Leaf! Record 'ce'.
  11. Backtrack and choose 'f' → path=['c', 'f']. Leaf! Record 'cf'.
  12. All combinations generated. Return ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'] (9 combinations total).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Letter Combinations of a Phone Number in the editorAll Backtracking problemsBack to roadmap