Letter Combinations of a Phone Number

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.

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;
    }
};