/**
knakul853
**/

class Solution {
public:
    vector<string> letterCombinations(string digits) {

        map<int,string>mp;
        mp[3]="def";mp[2]="abc";mp[4]="ghi";mp[5]="jkl";mp[6]="mno";

        if(digits.size()==0)return {};
        mp[7]="pqrs";mp[8]="tuv";mp[9]="wxyz";

        vector<string>ans;
        string temp;

        backtrack(digits , ans , mp , 0 , temp);

        return ans;
    }

    void backtrack(string& digits , vector<string>& ans , map<int,string>mp , int id , string temp)
    {
        if(temp.size() == digits.size())
        {
            ans.push_back(temp);
            return;
        }
        for(int i=id;i<digits.size();i++)
        {
            string s1 = mp[digits[i]-'0'];
            for(int j=0;j<s1.size();j++)
            {
                string keep = temp;
                temp = temp+string(1,s1[j]);
                backtrack(digits , ans , mp , i + 1 , temp);

                temp = keep;
            }
        }

    }
};