题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"
例如，给定 digits = "23"，返回 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
注意：2 对应的字母是 "abc"，3 对应的字母是 "def"，以此类推。每个数字可以对应 3 到 4 个字母。
解题思路：
本题通过回溯算法（Backtracking）来求解。回溯算法是一种通过递归的方法尝试所有可能的解，并在发现无解时回退的算法。回溯的思想很适合这种生成所有可能组合的题目。
步骤概述：
数字映射字母：我们首先创建一个映射关系，数字和字母的对应关系被存储在一个
Map中。例如，数字2映射到字母字符串"abc"，数字3映射到字母字符串"def"，等等。回溯算法：从字符串的第一个数字开始，递归地遍历每个数字对应的所有字母，将每个字母依次添加到当前组合中。当遍历完所有数字后，将组合添加到结果列表中。
结束条件：当遍历到数字字符串的末尾时，表示已经生成了一个有效的字母组合，将其加入结果列表。
回溯算法的详细步骤：
初始化：
创建一个
Map存储数字到字母的映射。创建一个空的
List<String>来存储最终的字母组合结果。
回溯函数：
使用递归的方式遍历每个数字对应的所有字母，逐个将字母加入当前组合（使用
StringBuffer以提高效率）。当递归到达数字字符串的末尾时，表示已经生成了一个有效的字母组合，将其添加到结果列表中。
在递归返回时，撤销上一步的操作（即删除最后加入的字母），尝试其他字母。
终止条件：
当递归到达数字字符串的末尾时，表示已经生成了一种组合，返回并保存结果。
代码实现：
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if(digits.length() == 0){
return combinations; // 如果输入为空，直接返回空结果
}
// 创建数字到字母的映射关系
Map<Character,String> map = new HashMap<>();
map.put('2',"abc");
map.put('3',"def");
map.put('4',"ghi");
map.put('5',"jkl");
map.put('6',"mno");
map.put('7',"pqrs");
map.put('8',"tuv");
map.put('9',"wxyz");
// 调用回溯算法
backtracking(combinations, digits, 0, map, new StringBuffer());
return combinations;
}
// 回溯算法
public void backtracking(List<String> combinations, String digits, int index, Map<Character, String> map, StringBuffer combination) {
// 回溯结束条件：当index等于字符串长度时，表示我们已经完成了一个字母组合
if(index == digits.length()) {
combinations.add(combination.toString()); // 将组合添加到结果集
} else {
// 获取当前数字对应的字母
char digit = digits.charAt(index);
String letters = map.get(digit);
for(int i = 0; i < letters.length(); i++) {
combination.append(letters.charAt(i)); // 将字母加入组合
backtracking(combinations, digits, index + 1, map, combination); // 递归调用处理下一个数字
combination.deleteCharAt(combination.length() - 1); // 撤销操作，回到上一步
}
}
}
}
代码解析：
主函数
letterCombinations：检查
digits是否为空。如果为空，直接返回空列表。初始化数字到字母的映射
map。调用回溯函数
backtracking，开始递归生成字母组合。
回溯函数
backtracking：index表示当前处理到数字字符串的哪个位置。当
index等于digits.length()时，表示已经生成一个完整的字母组合，将其添加到结果集combinations中。否则，遍历当前数字对应的所有字母，将字母依次加入当前的组合（
combination），然后递归地处理下一个数字。回溯时，撤销上一步的字母，恢复组合状态，继续尝试其他字母。
递归与回溯：
递归的核心思想是逐步选择每个数字对应的字母，直到遍历完所有数字。
回溯的关键是撤销上一步的选择（通过
combination.deleteCharAt()），以便尝试其他可能的字母。
时间复杂度分析：
假设输入的数字串长度为 n，每个数字最多对应 4 个字母（如数字 7 和 9），最少对应 3 个字母（如数字 2 到 6）。
每次递归调用中，我们要遍历当前数字对应的所有字母，因此每次递归的时间复杂度为
O(3)或O(4)。总的递归深度是
n（因为我们递归到数字串的末尾），因此总的时间复杂度是O(4^n)，即每个数字有 4 种可能字母，递归深度为n。
空间复杂度：
回溯过程中会维护一个字符串
combination，其大小最大为n。因此空间复杂度为O(n)。结果集
combinations存储了所有字母组合，大小为4^n，因此空间复杂度为O(4^n)。
总结：
本题通过回溯算法（Backtracking）高效地生成所有可能的字母组合。
回溯算法利用递归的思想，在逐步构建字母组合的过程中，保持对状态的控制，直到所有可能的组合都生成完毕。
该算法的时间复杂度较高，但适用于这类需要生成所有组合或排列的问题。