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

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

示例 1：

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

示例 2：

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

解题思路

回溯

1. 建立映射关系：用数组或哈希表将数字 2-9 映射到对应的字母集。
2. 确定递归函数的参数：记录当前遍历到了输入字符串的哪一个数字（即index），以及当前已经拼接好的字母组合path（可以使用StringBuilder以提高效率）。
3. 明确终止条件：当 index 等于输入字符串的长度
4. 执行单层搜索逻辑：
   • 取出当前index指向的数字。
   • 查找该数字对应的字母集。
   • 遍历这些字母，将每个字母拼接到当前的组合中。
   • 递归调用自身，处理下一个数字（index + 1）。
   • 回溯（撤销选择）：当递归返回后，我们需要把刚才添加的字母删掉，以便尝试当前数字对应的下一个字母。

Java实现

class Solution {

    private final String[] letterMap = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        if (digits == null || digits.length() == 0){
            return res;
        }
        backTrack(digits, 0, res, path);
        return res;
    }

    private void backTrack(String digits, int index, List<String> res, StringBuilder path){
        if (index == digits.length()){
            res.add(path.toString());
            return;
        }

        int number = digits.charAt(index) - '0';
        String letters = letterMap[number];

        for (int i = 0; i < letters.length(); i++){
            path.append(letters.charAt(i));
            backTrack(digits, index+1, res, path);
            path.deleteCharAt(path.length()-1);
        }

    }
}