DSA

Letter Combinations of a Phone Number

Miscellaneous problem — solution with code and analysis.

August 8, 2026
PatternBacktracking
Solve on LeetCode
Key insighttry it first, then reveal

Each digit maps to 2–4 letters, and you must pick exactly one letter per digit in order.

Given a string containing digits from 2–9 inclusive, return all possible letter combinations that the number could represent, just like on a telephone keypad.

Approach (Backtracking)#

  • Intuition: Each digit maps to 2–4 letters, and you must pick exactly one letter per digit in order. This is a classic Cartesian product problem — the total number of combinations is the product of the mapping sizes. Backtracking naturally generates each combination by building it one character at a time and undoing the last choice to try the next option.
  • Mechanics: A recursive helper takes the current digit index idx and a running path string. For each letter mapped to digits[idx], the letter is appended to path, the helper recurses on idx+1, then the letter is popped (backtrack). When path.length() == digits.size(), a complete combination is recorded.
  • Trade-off: The output size is inherently exponential — O(4^n) combinations of length n in the worst case (all 9s, each with 4 letters). Time and space are both O(4^n × n), which is unavoidable since every combination must be generated. The hash map lookup for each digit is O(1) and adds negligible overhead.
cpp
class Solution {
public:
    void findCombinations(string &digits, int idx, string &path, vector<string> &res, unordered_map<char, string> &phoneMap)
    {
        if(path.length()==digits.size()){
            res.push_back(path);
            return;
        }

        for(char ch: phoneMap[digits[idx]])
        {
            path.push_back(ch);
            findCombinations(digits, idx+1, path, res, phoneMap);
            path.pop_back();
        }
    }

    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> res;
        string path = "";
        findCombinations(digits, 0, path, res, phoneMap);
        return res;
    }
};