给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> coms;
        if(digits.empty()){
            return coms;
        }
        unordered_map<char,string> phoneMap{
            {'2',"abc"},
            {'3',"def"},
            {'4',"ghi"},
            {'5',"jkl"},
            {'6',"mno"},
            {'7',"pqrs"},
            {'8',"tuv"},
            {'9',"wxyz"}
        };
        string com;
        backtrack(coms,phoneMap,digits,0,com);
        return coms;
    }
    void backtrack(vector<string>& coms,const unordered_map<char,string>& phoneMap,const string& digits,int index,string& com){
        if(index==digits.size()){
            coms.push_back(com);
        }else{
            char digit=digits[index];
            const string& letters=phoneMap.at(digit);
            for(const char& letter:letters){
                com.push_back(letter);
                backtrack(coms,phoneMap,digits,index+1,com);
                com.pop_back();
            }
        }
    }
};

整体来说这道题的思路是枚举，只不过用回溯法去降低时间复杂度。用哈希表存储所有数字字符对应的字母的可能性，然后遍历字符。比如给出的字符为“23”，那么我们先去找到2对应的字母为abc，找到之后先对a进行处理，递归进入的是3对应的字符“def”，但是递归这里有点难想，进入递归之后相当于进入一次嵌套循环（我是这里理解的），然后遍历def，d完成遍历后，index等于digits的长度，coms则添加第一个结果字符ad，然后此时回到上次递归状态，注意此时是第3次使用backtrack，因此我们回到第二次调用，即遍历def的时候，先释放掉com，再继续遍历e，直到遍历完成。同样的遍历完def之后，回到上一层，继续遍历a的下一个，也就是b，直到全部情况遍历完成。其实递归的作用就有点类似于嵌套循环的过程，但是这里的index没有重置，因为递归的情况下，它退回上一层状态，相当于自动重置。