Letter Combinations of a Phone Number

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent on a traditional phone keypad.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

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

What to notice first

• The number of combinations grows exponentially: digits “23” produces 3 × 3 = 9 combinations.
• You must explore all possible paths through the digit-to-letter mapping.
• This is a classic exploration problem solved by backtracking or BFS.

Examples

Input	Output	Explanation
"23"	["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]	2 maps to “abc”, 3 maps to “def”; all pairings
""	[]	Empty input yields empty result
"2"	["a", "b", "c"]	Single digit maps directly to its letters
"234"	27 combinations	3 × 3 × 3 = 27 total combinations

Constraints

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9']

Real-World Applications

Where this pattern appears

• Predictive text / autocomplete — phone keyboards and T9 input systems generate word suggestions from digit sequences.
• Password generation patterns — exploring all possible character sequences for brute-force testing or policy compliance validation.
• Telephony routing — mapping numeric sequences to multiple possible extension names or office destinations.
• Chess move enumeration — generating all legal move combinations from a numeric board position encoding.

Complexity Comparison

Approach	Time	Space	Returns	Best When
Backtracking (Recursive)	O(4^n)	O(4^n)	All combinations	Want clear recursive structure, understanding decision tree
BFS (Iterative)	O(4^n)	O(4^n)	All combinations	Prefer iterative approach, level-by-level exploration

Which approach should you learn first?

• Pick Backtracking if you are learning recursion and decision trees.
• Pick BFS if you prefer iterative solutions or want to see level-by-level growth.

Most Common

Backtracking

O(4^n) time · O(4^n) space

Iterative

BFS

O(4^n) time · O(4^n) space

Approach 1: Backtracking (Recommended)

★ Recommended

Build combinations by recursively appending letters. For each digit, try all letters it maps to, then recurse on the next digit. When all digits are processed, save the combination.

The key insight is that we make a choice at each digit (which letter to use) and then recursively solve the subproblem for the remaining digits.

⏱ Time O(4^n) 4^n combinations 💾 Space O(4^n) Result storage

Step-by-step Example

Input: digits = "23"

Depth	Digit	Current	Action
0	”2"	""	Start backtracking
1	”3"	"a”	Process 2 → “a”, now explore 3
2	-	”ad”	Process 3 → “d”, save “ad” ✓
2	-	”ae”	Process 3 → “e”, save “ae” ✓
2	-	”af”	Process 3 → “f”, save “af” ✓
1	”3"	"b”	Backtrack to 2 → “b”, now explore 3
2	-	”bd”	Process 3 → “d”, save “bd” ✓
…	…	…	Continue for “c” + all letters in “def”

Pseudocode

function letterCombinationsBacktracking(digits):
    if digits is empty:
        return []

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

    result = []

    function backtrack(index, current):
        if index == len(digits):
            result.append(current)
            return

        digit = digits[index]
        letters = phoneMap[digit]
        for letter in letters:
            backtrack(index + 1, current + letter)

    backtrack(0, "")
    return result

Solution Code

Python

letter_combinations_backtracking.py

from typing import List


def letter_combinations_backtracking(digits: str) -> List[str]:
    """
    Generate all letter combinations using backtracking (recursive).
    Time: O(4^n), Space: O(4^n) for result
    """
    if not digits:
        return []

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

    result = []

    def backtrack(index: int, current_combination: str) -> None:
        # Base case: we've processed all digits
        if index == len(digits):
            result.append(current_combination)
            return

        # Get the letters that the current digit maps to
        current_digit = digits[index]
        letters = phone_map[current_digit]

        # Try each letter
        for letter in letters:
            backtrack(index + 1, current_combination + letter)

    backtrack(0, "")
    return result


print(letter_combinations_backtracking("23"))  # ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
print(letter_combinations_backtracking(""))  # []
print(letter_combinations_backtracking("2"))  # ["a", "b", "c"]

C++

letter_combinations_backtracking.cpp

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

class Solution {
public:
    /**
     * Generate all letter combinations using backtracking (recursive).
     * Time: O(4^n), Space: O(4^n) for result
     */
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

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

        vector<string> result;
        backtrack(digits, 0, "", result, phoneMap);
        return result;
    }

private:
    void backtrack(const string& digits, int index, string current,
                   vector<string>& result,
                   const unordered_map<char, string>& phoneMap) {
        // Base case: we've processed all digits
        if (index == digits.length()) {
            result.push_back(current);
            return;
        }

        // Get the letters that the current digit maps to
        char currentDigit = digits[index];
        const string& letters = phoneMap.at(currentDigit);

        // Try each letter
        for (char letter : letters) {
            backtrack(digits, index + 1, current + letter, result, phoneMap);
        }
    }
};

// Test
int main() {
    Solution sol;
    vector<string> result = sol.letterCombinations("23");
    // Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
    return 0;
}

Java

LetterCombinationsBacktracking.java

import java.util.*;

public class LetterCombinationsBacktracking {
    /**
     * Generate all letter combinations using backtracking (recursive).
     * Time: O(4^n), Space: O(4^n) for result
     */
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return new ArrayList<>();

        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), result, phoneMap);
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder current,
                          List<String> result, Map<Character, String> phoneMap) {
        // Base case: we've processed all digits
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        // Get the letters that the current digit maps to
        char currentDigit = digits.charAt(index);
        String letters = phoneMap.get(currentDigit);

        // Try each letter
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(digits, index + 1, current, result, phoneMap);
            current.deleteCharAt(current.length() - 1);
        }
    }

    public static void main(String[] args) {
        LetterCombinationsBacktracking sol = new LetterCombinationsBacktracking();
        System.out.println(sol.letterCombinations("23"));
        // Output: [ad, ae, af, bd, be, bf, cd, ce, cf]
    }
}

JavaScript

letter_combinations_backtracking.js

/**
 * Generate all letter combinations using backtracking (recursive).
 * Time: O(4^n), Space: O(4^n) for result
 * @param {string} digits
 * @return {string[]}
 */
function letterCombinationsBacktracking(digits) {
    if (!digits) return [];

    const phoneMap = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    };

    const result = [];

    function backtrack(index, currentCombination) {
        // Base case: we've processed all digits
        if (index === digits.length) {
            result.push(currentCombination);
            return;
        }

        // Get the letters that the current digit maps to
        const currentDigit = digits[index];
        const letters = phoneMap[currentDigit];

        // Try each letter
        for (const letter of letters) {
            backtrack(index + 1, currentCombination + letter);
        }
    }

    backtrack(0, "");
    return result;
}

console.log(letterCombinationsBacktracking("23"));
// Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Rust

letter_combinations_backtracking.rs

use std::collections::HashMap;

pub fn letter_combinations_backtracking(digits: String) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }

    let mut phone_map = HashMap::new();
    phone_map.insert('2', "abc");
    phone_map.insert('3', "def");
    phone_map.insert('4', "ghi");
    phone_map.insert('5', "jkl");
    phone_map.insert('6', "mno");
    phone_map.insert('7', "pqrs");
    phone_map.insert('8', "tuv");
    phone_map.insert('9', "wxyz");

    let mut result = vec![];
    backtrack(&digits, 0, String::new(), &mut result, &phone_map);
    result
}

fn backtrack(
    digits: &str,
    index: usize,
    current: String,
    result: &mut Vec<String>,
    phone_map: &HashMap<char, &'static str>,
) {
    // Base case: we've processed all digits
    if index == digits.len() {
        result.push(current);
        return;
    }

    // Get the letters that the current digit maps to
    let current_digit = digits.chars().nth(index).unwrap();
    let letters = phone_map[&current_digit];

    // Try each letter
    for letter in letters.chars() {
        backtrack(
            digits,
            index + 1,
            format!("{}{}", current, letter),
            result,
            phone_map,
        );
    }
}

fn main() {
    let result = letter_combinations_backtracking("23".to_string());
    println!("{:?}", result);
    // Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
}

Go

letter_combinations_backtracking.go

package main

import "fmt"

func letterCombinationsBacktracking(digits string) []string {
  if digits == "" {
    return []string{}
  }

  phoneMap := map[byte]string{
    '2': "abc",
    '3': "def",
    '4': "ghi",
    '5': "jkl",
    '6': "mno",
    '7': "pqrs",
    '8': "tuv",
    '9': "wxyz",
  }

  var result []string

  var backtrack func(int, string)
  backtrack = func(index int, current string) {
    // Base case: we've processed all digits
    if index == len(digits) {
      result = append(result, current)
      return
    }

    // Get the letters that the current digit maps to
    currentDigit := digits[index]
    letters := phoneMap[currentDigit]

    // Try each letter
    for _, letter := range letters {
      backtrack(index+1, current+string(letter))
    }
  }

  backtrack(0, "")
  return result
}

func main() {
  fmt.Println(letterCombinationsBacktracking("23"))
  // Output: [ad ae af bd be bf cd ce cf]
}

Approach 2: BFS (Level-Order Iteration)

🎯 Interview Favourite

Build combinations iteratively, processing one digit at a time. Start with a queue containing an empty string. For each digit, create new combinations by appending each of its letters to all current combinations.

This approach grows the result level by level, making it intuitive for those who prefer iterative over recursive solutions.

⏱ Time O(4^n) 4^n combinations 💾 Space O(4^n)

Step-by-step Example

Input: digits = "23"

Digit	Queue Before	Queue After	Action
”2”	[""]	["a", "b", "c"]	Append each of “abc” to ""
"3”	["a", "b", "c"]	["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]	Append each of “def” to each in queue

Pseudocode

function letterCombinationsBFS(digits):
    if digits is empty:
        return []

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

    queue = [""]

    for digit in digits:
        newQueue = []
        letters = phoneMap[digit]
        for current in queue:
            for letter in letters:
                newQueue.append(current + letter)
        queue = newQueue

    return queue

Solution Code

Python

letter_combinations_bfs.py

from typing import List
from collections import deque


def letter_combinations_bfs(digits: str) -> List[str]:
    """
    Generate all letter combinations using BFS (iterative).
    Time: O(4^n), Space: O(4^n) for result
    """
    if not digits:
        return []

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

    # Start with an empty combination
    queue = deque([""])

    for digit in digits:
        size = len(queue)
        letters = phone_map[digit]

        # Process all current combinations
        for _ in range(size):
            current = queue.popleft()
            # Create a new combination for each letter
            for letter in letters:
                queue.append(current + letter)

    return list(queue)


print(letter_combinations_bfs("23"))  # ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
print(letter_combinations_bfs(""))  # []
print(letter_combinations_bfs("2"))  # ["a", "b", "c"]

C++

letter_combinations_bfs.cpp

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

class Solution {
public:
    /**
     * Generate all letter combinations using BFS (iterative).
     * Time: O(4^n), Space: O(4^n) for result
     */
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

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

        queue<string> q;
        q.push("");

        for (char digit : digits) {
            int size = q.size();
            const string& letters = phoneMap[digit];

            // Process all current combinations
            for (int i = 0; i < size; i++) {
                string current = q.front();
                q.pop();

                // Create a new combination for each letter
                for (char letter : letters) {
                    q.push(current + letter);
                }
            }
        }

        vector<string> result;
        while (!q.empty()) {
            result.push_back(q.front());
            q.pop();
        }
        return result;
    }
};

// Test
int main() {
    Solution sol;
    vector<string> result = sol.letterCombinations("23");
    // Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
    return 0;
}

Java

LetterCombinationsBFS.java

import java.util.*;

public class LetterCombinationsBFS {
    /**
     * Generate all letter combinations using BFS (iterative).
     * Time: O(4^n), Space: O(4^n) for result
     */
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return new ArrayList<>();

        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        Queue<String> queue = new LinkedList<>();
        queue.offer("");

        for (char digit : digits.toCharArray()) {
            int size = queue.size();
            String letters = phoneMap.get(digit);

            // Process all current combinations
            for (int i = 0; i < size; i++) {
                String current = queue.poll();

                // Create a new combination for each letter
                for (char letter : letters.toCharArray()) {
                    queue.offer(current + letter);
                }
            }
        }

        return new ArrayList<>(queue);
    }

    public static void main(String[] args) {
        LetterCombinationsBFS sol = new LetterCombinationsBFS();
        System.out.println(sol.letterCombinations("23"));
        // Output: [ad, ae, af, bd, be, bf, cd, ce, cf]
    }
}

JavaScript

letter_combinations_bfs.js

/**
 * Generate all letter combinations using BFS (iterative).
 * Time: O(4^n), Space: O(4^n) for result
 * @param {string} digits
 * @return {string[]}
 */
function letterCombinationsBFS(digits) {
    if (!digits) return [];

    const phoneMap = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    };

    let queue = [""];

    for (const digit of digits) {
        const newQueue = [];
        const letters = phoneMap[digit];

        // Process all current combinations
        for (const current of queue) {
            // Create a new combination for each letter
            for (const letter of letters) {
                newQueue.push(current + letter);
            }
        }

        queue = newQueue;
    }

    return queue;
}

console.log(letterCombinationsBFS("23"));
// Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Rust

letter_combinations_bfs.rs

use std::collections::{HashMap, VecDeque};

pub fn letter_combinations_bfs(digits: String) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }

    let mut phone_map = HashMap::new();
    phone_map.insert('2', "abc");
    phone_map.insert('3', "def");
    phone_map.insert('4', "ghi");
    phone_map.insert('5', "jkl");
    phone_map.insert('6', "mno");
    phone_map.insert('7', "pqrs");
    phone_map.insert('8', "tuv");
    phone_map.insert('9', "wxyz");

    let mut queue = VecDeque::new();
    queue.push_back(String::new());

    for digit in digits.chars() {
        let size = queue.len();
        let letters = phone_map[&digit];

        // Process all current combinations
        for _ in 0..size {
            let current = queue.pop_front().unwrap();

            // Create a new combination for each letter
            for letter in letters.chars() {
                queue.push_back(format!("{}{}", current, letter));
            }
        }
    }

    queue.into_iter().collect()
}

fn main() {
    let result = letter_combinations_bfs("23".to_string());
    println!("{:?}", result);
    // Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
}

Go

letter_combinations_bfs.go

package main

import "fmt"

func letterCombinationsBFS(digits string) []string {
  if digits == "" {
    return []string{}
  }

  phoneMap := map[byte]string{
    '2': "abc",
    '3': "def",
    '4': "ghi",
    '5': "jkl",
    '6': "mno",
    '7': "pqrs",
    '8': "tuv",
    '9': "wxyz",
  }

  queue := []string{""}

  for i := 0; i < len(digits); i++ {
    digit := digits[i]
    letters := phoneMap[digit]

    var newQueue []string

    // Process all current combinations
    for _, current := range queue {
      // Create a new combination for each letter
      for _, letter := range letters {
        newQueue = append(newQueue, current+string(letter))
      }
    }

    queue = newQueue
  }

  return queue
}

func main() {
  fmt.Println(letterCombinationsBFS("23"))
  // Output: [ad ae af bd be bf cd ce cf]
}

Common mistakes

Watch for these pitfalls

• Forgetting to handle the empty string case (return [], not [""]).
• Using a static phone map incorrectly (ensure digit ‘0’ and ‘1’ are not included or handled separately).
• In the BFS approach, clearing the queue without saving it first (always save results before processing the next digit).
• Off-by-one errors in the backtracking base case (ensure index == len(digits), not index > len(digits)).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

letter_combinations_of_a_phone_number_space_optimized.py

"""
Solution for Letter Combinations of a Phone Number
"""

def solve():
    """Implementation for approach 3 of Letter Combinations of a Phone Number"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

letter_combinations_of_a_phone_number_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Letter Combinations of a Phone Number
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

LetterCombinationsOfAPhoneNumberSpaceOptimized.java

/**
 * Solution for Letter Combinations of a Phone Number
 * Approach 3
 */
public class LetterCombinationsOfAPhoneNumberSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

letter_combinations_of_a_phone_number_space_optimized.js

/**
 * Solution for Letter Combinations of a Phone Number
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

letter_combinations_of_a_phone_number_space_optimized.rs

/// Solution for Letter Combinations of a Phone Number
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

letter_combinations_of_a_phone_number_space_optimized.go

package main

import "fmt"

// Solution for Letter Combinations of a Phone Number
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Combinations ↗ Medium #77
• Permutations ↗ Medium #46
• Combination Sum ↗ Medium #39
• Permutation Sequence ↗ Hard #60

Interview Tips

Key trade-offs to discuss

• Backtracking vs BFS: Both are O(4^n) time and space. Backtracking is more natural for recursive explorers; BFS is better if you want to demonstrate understanding of level-order growth.
• Edge cases: Emphasize that empty input should return an empty list, not a list with one empty string.
• Phone keypad knowledge: Be ready to explain why digits 0 and 1 are not included (historically, they had no letters on phone keypads).
• Follow-up — K-digit combinations: If asked to generate only k-length combinations, add a parameter and check len(current) == k before saving.

← Previous
#16 3Sum Closest Next
#18 4Sum →