class Solution {
public:
    vector<string> result;
    string path = "";
    unordered_map<char, string> num2alpha;

    void backtracking(const string& digits, int index) {
        if(index == digits.size()) {
            result.emplace_back(path);
            return;
        }

        for(char c : num2alpha[digits[index]]) {
            path.push_back(c);
            backtracking(digits, index + 1);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        num2alpha['2'] = "abc";
        num2alpha['3'] = "def";
        num2alpha['4'] = "ghi";
        num2alpha['5'] = "jkl";
        num2alpha['6'] = "mno";
        num2alpha['7'] = "pqrs";
        num2alpha['8'] = "tuv";
        num2alpha['9'] = "wxyz";

        backtracking(digits, 0);
        return result;
    }
};