Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent based on standard telephone keypad mapping. Note that digit 1 does not map to any letters.

Problem Analysis

Each digit expands to multiple characters, creating a combinatorial explosion. For input "23", the digit 2 yields {a, b, c} and 3 yields {d, e, f}, producing nine total combinations through their Cartesian product. An empty input string should return an empty collection.

Solution Strategy

This problem exhibits optimal substructure suitable for depth-first search with backtracking. The search space forms a tree where depth corresponds to digit position and branching factor equals the number of letters mapped to that digit.

The algorithm maintains a temporary buffer representing the current path from root to the current node. At each recursion level:

1. If the buffer length matches the input length, the current permutation is complete—add it to the results and terminate this branch.
2. Otherwise, retrieve the character set for the digit at the current index.
3. Iterate through each character in that set: append it to the buffer, recurse to process the next digit position, then remove the character to restore state for sibling branches.

Since every digit-to-letter selection produces a valid solution, no pruning logic is necessary—simple exhaustive enumeration suffices.

Reference Implementation

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.empty()) {
            return result;
        }
        
        const vector<string> keypad = {
            "", "", "abc", "def", "ghi", "jkl", 
            "mno", "pqrs", "tuv", "wxyz"
        };
        string path;
        dfs(digits, 0, keypad, path, result);
        return result;
    }

private:
    void dfs(const string& digits, int idx, const vector<string>& keypad, 
             string& path, vector<string>& result) {
        if (idx == digits.size()) {
            result.push_back(path);
            return;
        }
        
        int num = digits[idx] - '0';
        for (char ch : keypad[num]) {
            path.push_back(ch);
            dfs(digits, idx + 1, keypad, path, result);
            path.pop_back();
        }
    }
};

Complexity Analysis

Let $M$ denote the quantity of digits that map to 3 letters (2, 3, 4, 5, 6, 8) and $N$ denote the quantity mapping to 4 letters (7, 9), where $M + N$ equals the total input length.

Time Complexity: $O(3^M \times 4^N)$ — The algorithm generates exactly the Cartesian product of all character sets, visiting each of the $3^M \times 4^N$ possible combinations once.

Space Complexity: $O(M + N)$ — Excluding the output storage, auxiliary space comprises the recursion stack (maximum depth $M + N$) and the keypad lookup table ($O(1)$ fixed size). The temporary path string also consumes $O(M + N)$ space.