Letter Combinations of a Phone Number: Index Backtracking

Intermediate 8 min read

What you'll learn

✓How to set up the digit-to-letters map cleanly
✓A backtracking template indexed by digit position
✓How to handle empty input and invalid digits
✓The exact 3^n * 4^m complexity bound
✓How to talk about iterative vs recursive trade-offs

Prerequisites

•Comfort with [recursion](/blog/recursion-fundamentals)
•Familiarity with [hash maps](/blog/hashing-and-hash-maps)

Letter Combinations of a Phone Number is the simplest backtracking problem on the list. It is also the cleanest place to practice index-based recursion before tackling harder enumeration problems.

The Problem

Given a string of digits 2-9, return all letter combinations that the digits could represent on a classic phone keypad.

Example:

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

The mapping: 2 maps to abc, 3 to def, 4 to ghi, 5 to jkl, 6 to mno, 7 to pqrs, 8 to tuv, 9 to wxyz.

Intuition

Each digit independently chooses one of its 3 or 4 letters, so the answer is the Cartesian product of the per-digit letter sets. Cartesian products are naturally expressed as nested loops, but the digit count is variable, so recursion replaces the nesting: at depth i pick a letter for digits[i] and recurse on i + 1. At depth equal to the input length, emit the accumulated string.

Explanation with Example

digits = "23".

i=0, digit 2, letters abc.
- Pick a, recurse on i=1.
  - i=1, digit 3, letters def.
    - Pick d: path [a,d]. Record "ad".
    - Pick e: record "ae".
    - Pick f: record "af".
- Pick b: record "bd", "be", "bf".
- Pick c: record "cd", "ce", "cf".

Nine combinations.

                       ""
      +--------------+--------------+
     "a"            "b"            "c"
    / | \          / | \          / | \
  ad ae af       bd be bf       cd ce cf

Depth equals len(digits); branching equals letters per digit.

Recursion tree for digits='23' (2 -> abc, 3 -> def)

Code

Backtrack one digit at a time, appending a letter and recursing on the next digit. Linear recursion depth, branching factor 3 or 4 per digit.

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    }
    result = []
    path = []

    def backtrack(i):
        if i == len(digits):
            result.append(''.join(path))
            return
        for letter in mapping[digits[i]]:
            path.append(letter)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

import java.util.*;

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

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || 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;
        }
        String letters = MAP[digits.charAt(i) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(digits, i + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.empty()) return result;
        string path;
        backtrack(digits, 0, path, result);
        return result;
    }

private:
    const vector<string> MAP = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    void backtrack(const string& digits, int i, string& path, vector<string>& result) {
        if (i == (int)digits.size()) {
            result.push_back(path);
            return;
        }
        const string& letters = MAP[digits[i] - '0'];
        for (char c : letters) {
            path.push_back(c);
            backtrack(digits, i + 1, path, result);
            path.pop_back();
        }
    }
};

Edge Cases

Empty string: return [] per the problem statement.
Digit 1 or 0: the standard keypad has no letters; assume input excludes them as the constraints say. If you must handle them, treat them as a no-op or error.
Long inputs: result size grows multiplicatively. 4 digits all mapping to 4-letter keys produce 256 results.
Repeated digits like “77”: still enumerates 16 strings.

Complexity Analysis

Time: O(3^n * 4^m) where n is the count of digits that map to 3 letters and m the count of digits that map to 4 letters. Each combination takes O(n+m) to build.
Space: O(n + m) recursion depth, plus output size.

This is also the output size, so it’s a tight bound.

How to Explain It in an Interview

Begin with the setup: “Each digit independently picks one of its 3 or 4 letters, so the total count is the product.” That motivates the index-based backtracking. Walk through one branch. Mention you could write an iterative BFS version that maintains a queue of partial strings; some interviewers prefer that, but recursion is cleaner. Call out the empty-string edge case explicitly.

Combination Sum
Subsets
Permutations
Generalized Abbreviation

Wrap up

Letter Combinations is the friendliest backtracking problem to practice clean recursion structure. Master it, and the harder enumeration problems become applications of the same template with extra constraints. Pair it with Big-O intuition to talk about why the output size dominates.