DSA AnimatorDSA animations
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
Recursion Tree
Tree will appear here
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.

How to solve Letter Combinations of a Phone Number

LeetCode 17 · Medium · Backtracking · Pattern: Backtracking on Digits

Why the obvious approach is slow

Nested loops only work when you know the number of digits. Recursion handles any length.

The key idea

Each level of the tree is one digit. At a level, try every letter of that digit, append it, and recurse. When the string is as long as the digits, record it.

Remember

One tree level per digit. The branching factor is the number of letters.

Run the animation above on your own input, or watch the 1:10 video explanation of Letter Combinations of a Phone Number with a dry run and Java code.

More Backtracking problems