Letter Combinations of a Phone Number

MediumBacktracking · Strings🧩 Backtracking LeetCode #17 ↗Updated Oct 30, 2026

Problem

On an old phone keypad each digit 2–9 stands for a few letters (2→abc, 3→def, …, 7→pqrs, 9→wxyz). Given a string digits, return every word you could type by picking one letter per digit, in any order. An empty input produces an empty list.

Inputdigits = "23"Output["ad","ae","af","bd","be","bf","cd","ce","cf"]

Inputdigits = ""Output[]

Inputdigits = "7"Output["p","q","r","s"]

0 ≤ digits.length ≤ 4 · each digit is in '2'..'9'

Try it yourself

Java

class Solution {
    public List<String> letterCombinations(String digits) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer is a Cartesian product of the digits' letter sets. Walk the digits left to right, choose one letter, recurse, then un-choose — one shared buffer builds every word.

PatternBacktracking

Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.

Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.

Open the Backtracking guide →

Approaches

Brute ForceIterative Layer Expansion

Time O(n · 4ⁿ)Space O(n · 4ⁿ)

Start with the list [""]. For each digit, replace the list with every old prefix extended by every letter of that digit. After the last digit the list holds all full words. Every intermediate layer is materialised as brand-new strings.

Java

private static final String[] KEYS =
    {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits.isEmpty()) return result;
    result.add("");
    for (char d : digits.toCharArray()) {
        List<String> next = new ArrayList<>();
        for (String prefix : result) {
            for (char letter : KEYS[d - '0'].toCharArray()) {
                next.add(prefix + letter); // new string per extension
            }
        }
        result = next;
    }
    return result;
}

Simple and loop-only, but builds and throws away every partial layer of strings.

OptimalBacktracking with One StringBuilder

Time O(n · 4ⁿ)Space O(n) extra

Depth i of the recursion decides the letter for digit i. Append a letter, recurse to the next digit, then delete it again so the same buffer is reused. A string is created only when the buffer reaches full length, so the only real cost is writing the output itself.

Java

private static final String[] KEYS =
    {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits.isEmpty()) return result;
    backtrack(digits, 0, new StringBuilder(), result);
    return result;
}

private void backtrack(String digits, int i, StringBuilder path, List<String> result) {
    if (i == digits.length()) {
        result.add(path.toString());
        return;
    }
    for (char letter : KEYS[digits.charAt(i) - '0'].toCharArray()) {
        path.append(letter);                 // choose
        backtrack(digits, i + 1, path, result);
        path.deleteCharAt(path.length() - 1); // un-choose
    }
}

Output-bound: no intermediate layers, just O(n) recursion depth plus the answer.

Pro tip

Say the bound out loud: at most 4ⁿ words of length n, so no algorithm can beat O(n · 4ⁿ) — the win is in avoiding wasted work.

At a glance

Level	Approach	Time	Space
Brute Force	Iterative Layer Expansion	`O(n · 4ⁿ)`	`O(n · 4ⁿ)`
Optimal	Backtracking with One StringBuilder	`O(n · 4ⁿ)`	`O(n) extra`

Common pitfalls

Returning [""] for empty input — the expected answer is an empty list.
Forgetting to remove the last char after recursing — words grow longer and longer.
Mapping 7 and 9 to three letters — they have four.

Interview tips

Draw the recursion tree for "23": depth = digit index, branches = letters.
Explain why both approaches share the same big-O: the output size dominates.
Mention the choose / explore / un-choose template — it reappears in subsets and permutations.

Pattern

Backtracking over a product space → when you must list every combination formed by one choice per position.

My notes saved in this browser