class Solution {
    string dig_to_char[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void backtrack(string &digits, int cur, string &temp, vector<string> &ans)
    {
        if(temp.length()==digits.length())
        {
            ans.push_back(temp);
            return;
        }
        for(int i=0; i < dig_to_char[digits[cur]-'2'].size(); i++)
        {
            temp.push_back(dig_to_char[(digits[cur]-'2')][i]);
            backtrack(digits, cur+1, temp, ans);
            temp.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits)
    {
        if(digits=="")
            return {};
        vector<string> ans;
        string temp = "";
        backtrack(digits, 0, temp, ans);
        return ans;
    }
};