class Solution {
public:
    vector<vector<int>> ans;     //储存结果
    vector<int> path;            //单个路径结果
    long long sum=0;
    void backtracking(int k,int n,int startindex)
    {
        if(path.size()==k)            //等于k的时候（k个数的集合），就开始返回了
        {
            if(sum==n)                //符合要求就收集，不然直接返回
            {
                ans.push_back(path);
            }
            return;
        }
        for(int i=startindex;i<=9;i++)        //注意因为只能选1-9九个数字
        {
            path.push_back(i);                //插入
            sum=sum+i;
            backtracking(k,n,i+1);
            path.pop_back();            //回溯
            sum=sum-i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,1);
        return ans;
    }
};

class Solution {
public:
    const string phonemap[10]={ "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
    };
    vector<string>ans;                        //收集答案
    string path;                                //收集字符
    void backtacking(string digits,int index)
    {
        if(digits.size()==index)       //index是储存按下数字数组的下标
        {
            ans.push_back(path);
            return;
        }
        int j=digits[index]-'0';            //转换成整型数字
        string lettermap=phonemap[j];        //找到按键数字所代表的字符串
        for(int i=0;i<lettermap.size();i++)        //遍历
        {
            path.push_back(lettermap[i]);
            backtacking(digits,index+1);
            path.pop_back();                //回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
        {
            return ans;
        }
        backtacking(digits,0);
        return ans;
    }
};