Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Letter Combinations of a Phone Number

LeetCode #17Medium

One digit per tree level

Given a string of digits 2–9, return all letter combinations the number could spell using the classic phone keypad mapping (2→abc, 3→def, …). Return them in any order.

Asked atAmazonGoogleMeta

Backtracking · one digit per level

time O(4ⁿ · n)space O(n)

step 1 / 27

solution-space tree

“ ”

combinations

(none yet)

Backtracking · one digit per level


▸
1combine(index, path):
2    if index == len(digits):
3        record path             // a full combination (leaf)
4        return
5    for letter in keypad[digits[index]]:
6        path.push(letter)       // choose
7        combine(index+1, path)  // explore next digit
8        path.pop()              // un-choose (backtrack)

state

digits"23"
2abc
3def

line 1Generate EVERY letter string for the phone digits "23". On a keypad 2→abc and 3→def, so each combination picks one letter from each digit. We descend the tree one DIGIT per level: level 1 chooses a letter of digit 2, level 2 a letter of digit 3.