← Back to DSA Animator
Letter Combinations of a Phone Number LC #17 Medium Backtracking · Phone Keypad
Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz.

Example 1
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 2→abc, 3→def → 3×3 = 9 combinations.
Example 2
Input: digits = ""
Output: []
Example 3
Input: digits = "2"
Output: ["a","b","c"]
Constraints: 0 ≤ digits.length ≤ 4  |  digits[i] is a digit in ['2','9'].
Try Examples
Custom:
Approach
Backtracking — Digit by Digit
For each digit position, try all its mapped letters (3-4 choices). Recurse to next digit position. Base: idx==digits.length → combination complete. Depth = digits.length.
Phone Keypad
Input Digits
Building String
(empty)
Results 0 found
Variables
idx
0
curr string
""
total found
0
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Map each digit to its letters (phone keypad mapping)
2
For each digit position (idx), try all its mapped letters
3
Base case: idx == digits.length → add built string to results
4
Depth = number of digits; branching = 3 or 4 per digit
Time
O(4^n · n)
Space
O(n)
Why Backtracking Works

For each digit we branch into 3-4 letters, going digit by digit. The recursion depth equals the number of digits. Total combinations = product of letter counts for each digit (e.g., "23" → 3×3 = 9). Since we're building the string immutably (concatenation), no explicit undo step is needed.