Coding interview problems › Backtracking

🧩 Backtracking Medium

Letter Combinations of a Phone Number

Letter Combinations of a Phone Number explained: backtracking over keypad digits to list every letter string, tested Python, pitfalls and a live visual.

Also searched as: phone keypad letter combinations · letter combinations backtracking · T9 keypad combinations

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

Watch the Backtracking lab grow its recursion tree one call at a time; here each level of that tree is one digit and its branches are the digit's letters.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Old phone keypads map digits 2 to 9 to letters (2 is abc, 3 is def, ..., 7 is pqrs, 9 is wxyz). Given a string of such digits, return every letter string the digits could spell. For an empty input, return an empty list.

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

The key insight

Each digit is one level of the recursion tree, and its letters are the branches. Pick a letter for the first digit, recurse on the rest, then try the next letter. When every digit has a letter, you have one complete combination.

Brute force first: Writing one nested loop per digit works only for a fixed length; recursion handles any length with the same code.

Step-by-step approach

  1. Store the keypad mapping in a dictionary.
  2. If the input is empty, return [].
  3. Define dfs(i): if i equals the number of digits, record the joined path.
  4. Otherwise, for each letter of digits[i]: append, call dfs(i + 1), pop.
  5. Call dfs(0).

Python solution

PYTHON 3tested
KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letter_combinations(digits):
    if not digits:
        return []
    out, path = [], []

    def dfs(i):
        if i == len(digits):
            out.append("".join(path))
            return
        for ch in KEYPAD[digits[i]]:
            path.append(ch)
            dfs(i + 1)
            path.pop()

    dfs(0)
    return out

Complexity

TimeO(n · 4^n)
SpaceO(n)

Each digit has at most 4 letters, so there are up to 4n strings, each of length n. The recursion is n deep.

Common mistakes

Frequently asked questions

What is the time and space complexity of Letter Combinations?

O(n × 4^n) time in the worst case, because there can be 4^n strings of length n. Extra space is O(n) for recursion apart from the output.

Can I solve it without recursion?

Yes. Start with [""] and for each digit replace the list with every existing string extended by every letter of that digit. itertools.product does the same in one line.

Why is this called backtracking if nothing is pruned?

It uses the same choose, explore, un-choose structure. There is no constraint to prune here, so every leaf of the tree is an answer.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.