Letter Combinations of a Phone Number

Think about the old phone keypads. The number 2 had the letters abc printed on it. The number 3 had def. This question takes a string of digits and asks for every word you could type. It is a clean way to practice building all combinations with backtracking. So it shows up in interviews a lot.

🎯 The Problem

You get a string of digits. Each digit maps to letters, like the old phone keypad. You return every letter string you can build.

The rules:

• The digit 2 gives a, b, or c. The digit 3 gives d, e, or f, and so on.
• Pick one letter for each digit, in order.
• Each finished string is one combination. One full pick, one letter per digit.
• An empty input string returns an empty list, not a list with one empty string.

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

Explanation: 2 -> abc, 3 -> def
Pick one letter from each digit and join them.

Here is the digit to letter map shown as a picture. Each digit points to its small set of letters.

🔁 Approach 1: Repeated Cartesian Product (Iterative)

The idea in one line: keep a list of strings so far, and for each new digit grow every string by each of its letters.

How it works:

• Start the list with one empty string.
• Read the next digit. Look up its letters.
• For every string in the list, append every letter to form new strings.
• Replace the list with the new, longer strings.
• Repeat for each digit.

Why it works:

• This is the same set of answers as the recursion, built layer by layer.
• It avoids the call stack.

Why it is heavier:

• It holds all partial strings of the current length in memory at once.
• Backtracking keeps only one path at a time, so it uses less space.

Here is the iterative product code for that idea:

def letter_combinations(digits):
    if not digits:
        return []

    phone = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    result = [""]
    for digit in digits:
        result = [prefix + ch for prefix in result for ch in phone[digit]]
    return result

⚡ Approach 2: Backtracking (Best)

The idea in one line: build the string one digit at a time, try each letter as a choice, then undo and try the next.

How it works:

• Start with an empty string. Look at the first digit.
• Try each of its letters. Add one, move to the next digit.
• Keep going until one letter sits for every digit. That finished string is one answer.

Why backtracking:

• At each digit there is a small set of letters. That is the choice.
• Picking one letter does not block the others.
• After exploring everything that starts with a, remove the a and try b.
• Add a letter, recurse, remove the letter. The classic add, recurse, remove pattern.

When a path finishes:

• The position we fill reaches the end of the digit string.
• The built string now has one letter per digit. Save it.

Steps to Solve

1. Build a map from each digit to its letters, like 2 to abc and 3 to def.
2. Start with an empty string and the first digit position.
3. If the position reached the end of the digits, save the built string and stop this path.
4. Look up the letters for the current digit.
5. For each letter, add it to the built string.
6. Recurse to the next digit position.
7. After the recursion returns, remove that letter so you can try the next one.

Here is the decision tree for 23. The first level picks a letter for 2. The second level picks a letter for 3.

#include <stdio.h>
#include <string.h>

const char *map[] = {
    "", "", "abc", "def", "ghi", "jkl",
    "mno", "pqrs", "tuv", "wxyz"
};

char digits[20];
int dlen;
char current[20];   // the string we are building

void backtrack(int index) {
    if (index == dlen) {        // placed a letter for every digit
        current[index] = '\0';
        printf("%s\n", current);
        return;
    }
    const char *letters = map[digits[index] - '0'];  // letters for this digit
    for (int i = 0; letters[i] != '\0'; i++) {
        current[index] = letters[i];   // add this letter
        backtrack(index + 1);          // move to next digit
        // no explicit remove needed: next loop overwrites this slot
    }
}

int main(void) {
    strcpy(digits, "23");
    dlen = strlen(digits);
    backtrack(0);
    return 0;
}

ad
ae
af
bd
be
bf
cd
ce
cf

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

unordered_map<char, string> keypad = {
    {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
    {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};

void backtrack(const string& digits, int index,
               string& current, vector<string>& result) {
    if (index == (int)digits.size()) {   // one letter per digit
        result.push_back(current);
        return;
    }
    string letters = keypad[digits[index]];   // letters for this digit
    for (char c : letters) {
        current.push_back(c);                 // add the letter
        backtrack(digits, index + 1, current, result);
        current.pop_back();                   // remove it (backtrack)
    }
}

int main() {
    string digits = "23";
    vector<string> result;
    string current = "";
    backtrack(digits, 0, current, result);
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << "\"" << result[i] << "\"";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    return 0;
}

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

import java.util.ArrayList;
import java.util.List;

public class LetterCombinations {
    static String[] keypad = {
        "", "", "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };

    static void backtrack(String digits, int index,
                          StringBuilder current, List<String> result) {
        if (index == digits.length()) {    // one letter per digit
            result.add(current.toString());
            return;
        }
        String letters = keypad[digits.charAt(index) - '0'];  // this digit
        for (int i = 0; i < letters.length(); i++) {
            current.append(letters.charAt(i));   // add the letter
            backtrack(digits, index + 1, current, result);
            current.deleteCharAt(current.length() - 1);  // backtrack
        }
    }

    public static void main(String[] args) {
        String digits = "23";
        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), result);
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < result.size(); i++) {
            sb.append("\"").append(result.get(i)).append("\"");
            if (i < result.size() - 1) sb.append(",");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

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

def letter_combinations(digits):
    if not digits:                 # no digits means no combinations
        return []
    keypad = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    result = []

    def backtrack(index, current):
        if index == len(digits):          # one letter per digit
            result.append("".join(current))
            return
        for letter in keypad[digits[index]]:  # letters for this digit
            current.append(letter)            # add the letter
            backtrack(index + 1, current)     # move to next digit
            current.pop()                     # remove it (backtrack)

    backtrack(0, [])
    return result


print(letter_combinations("23"))

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

function letterCombinations(digits) {
  if (digits.length === 0) return []; // no digits, no combinations
  const keypad = {
    2: "abc", 3: "def", 4: "ghi", 5: "jkl",
    6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz",
  };
  const result = [];

  function backtrack(index, current) {
    if (index === digits.length) {      // one letter per digit
      result.push(current.join(""));
      return;
    }
    for (const letter of keypad[digits[index]]) { // letters for this digit
      current.push(letter);             // add the letter
      backtrack(index + 1, current);    // move to next digit
      current.pop();                    // backtrack
    }
  }

  backtrack(0, []);
  return result;
}

console.log(letterCombinations("23"));

[
  'ad', 'ae', 'af',
  'bd', 'be', 'bf',
  'cd', 'ce', 'cf'
]

Let us read the Python version line by line. The shape is the classic backtracking template.

if not digits: is a guard. If the input string is empty there is nothing to build. So we return an empty list right away.

keypad = { ... } is our lookup table. Each digit string maps to its letters. This is just the old phone keypad written as a dictionary. We will read from it at each step.

if index == len(digits): is the stop condition. index is the digit position we are filling. When index reaches the length, we have chosen a letter for every digit. So the current list holds one complete combination.

result.append("".join(current)) saves that combination. The join turns the list of letters into one string. We store the string, so it stays safe even when current changes later.

for letter in keypad[digits[index]]: reads the letters for the current digit. digits[index] is the actual digit character. We look it up in the keypad to get its letters. Then we loop over each one.

current.append(letter) makes the choice. backtrack(index + 1, current) moves to the next digit and goes deeper. current.pop() undoes the choice. This pop is the backtrack. It removes the last letter so the loop can try the next one cleanly.

⏱️ Time and Space Complexity

Each digit has at most four letters, like the 7 and 9 keys. If there are n digits, the number of combinations is up to 4 to the power of n. For each finished combination we also spend O(n) to join the letters into a string. So the time is O(n × 4ⁿ). The recursion depth and the current string take O(n) space, not counting the output list.

🧩 Key Takeaways

• ✅ Map each digit to its letters first, just like the old phone keypad.
• ✅ Build the string one digit at a time, trying each letter as a choice.
• ✅ When the position reaches the end of the digits, save the built string.
• ✅ Add a letter, recurse to the next digit, then remove the letter to try the next one.
• ✅ Handle the empty input as a special case that returns an empty list.

🚀 What’s Next?

• Palindrome Partitioning
• Word Search