Letter Combinations of a Phone Number

Explanation & Solution

Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons):

2 → abc
3 → def
4 → ghi
5 → jkl
6 → mno
7 → pqrs
8 → tuv
9 → wxyz

Note that 1 does not map to any letters.

Examples

Example 1

Input: digits = "23"

Output:["ad","ae","af","bd","be","bf","cd","ce","cf"]

Explanation: Digit 2 maps to "abc" and digit 3 maps to "def", giving 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 the range ['2', '9']

Approach

Subsets pattern

1. Handle Empty Input

If digits is empty, return an empty array immediately

2. Build the Digit-to-Letter Map

Create a mapping object from each digit to its corresponding letters on a phone keypad

3. Backtrack Through Digits

At each index, look up the letters for digits[index]
Try each letter: append it to the current string and recurse to the next index

4. Collect Results

When index === digits.length, the current combination is complete — push it to result
No explicit backtracking (undo) is needed since we pass current + ch as a new string

🧠 Key Insight

Each digit maps to 3-4 letters, so the total combinations grow multiplicatively. For n digits, there are at most 4^n combinations.

Time

O(4^n × n) where n is the length of digits

Space

O(n) for the recursion stack

Visualization

Input:

Backtracking Exploration

current path

empty

No animation available

ExploringFoundBacktrack

0 steps

Solution Code

Combination Sum III

Generate Parentheses