Pattern visualizer
Letter Combinations of a Phone Number
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. Animated on: digits = "23" — return all possible letter combinations that the numbers could represent (2 maps to "abc", 3 maps to "def")..
Depth-first search over telephone keypad mappings
time O(4^n * n)space O(n)step 1 / 12
a
[0]line 8
idx=0 (digit '2' → 'abc'): choose letter 'a'. path = ['a']. Recurse to idx=1.
Pseudocode
1FUNCTION letterCombinations(digits):2 IF digits is empty: RETURN empty list3 phone = a table mapping each digit to its letters ('2'->'abc', '3'->'def')4 ans = empty list of results, path = empty current combination5 FUNCTION backtrack(idx):6 IF idx equals the length of digits: join path into a string and add it to ans; RETURN7 FOR each letter mapped to digits[idx]:8 add letter to path; backtrack(idx + 1); remove the last letter from path9 END FOR10 backtrack(0); RETURN ans
← / → step · space play · Home restart