17. 电话号码的字母组合
    给定一个仅包含数字 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’] 的一个数字。

//最基本的回溯算法，套用基本的回溯模板
// vector<vector> result;
// vector path;
// void backtracking(参数) {
// if (终止条件) {
// 存放结果;
// return;
// }

// for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
// 处理节点;
// backtracking(路径，选择列表); // 递归
// 回溯，撤销处理结果
// }
// }

//最基本的回溯算法，套用基本的回溯模板
// vector<vector<int>> result;
// vector<int> path;
// void backtracking(参数) {
//     if (终止条件) {
//         存放结果;
//         return;
//     }

//     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
//         处理节点;
//         backtracking(路径，选择列表); // 递归
//         回溯，撤销处理结果
//     }
// }
class Solution {
private:
    vector<string> letters_vector={
        "",//0
        "",//1
        "abc",//2
        "def",//3
        "ghi",//4
        "jkl",//5
        "mno",//6
        "pqrs",//7
        "tuv",//8
        "wxyz"//9
    };
    vector<string> result;//需要返回什么，就初始化什么
    string path;//每一步需要往result里装入什么就初始化什么
    void BackTracking(string& digits,int index)//两个参数，原本函数的参数引用，开始坐标
    {
        if(path.size()==digits.size())//回溯截至条件
        {
            result.push_back(path);
            return;
        }
        string letters=letters_vector[digits[index]-'0'];
        for(int i=0;i<letters.size();i++)//一层的宽度，用for循环实现
        {
            path.push_back(letters[i]);
            BackTracking(digits,index+1);//往下一层走
            path.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return result;
        BackTracking(digits,0);
        return result;
    }
};