题目
给定一个仅包含数字 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:
def letterCombinations(self, digits: str) -> List[str]:
# 创建数字到字母的映射，如电话按键
phone_map = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
def backtrack(index, path):
# 如果路径长度等于输入数字的长度，添加到结果中
if len(path) == len(digits):
combinations.append("".join(path))
return
# 获取当前数字对应的所有可能字母
possible_letters = phone_map[digits[index]]
# 遍历这些字母
for letter in possible_letters:
# 添加字母到当前路径并递归
path.append(letter)
backtrack(index + 1, path)
# 回溯，移除路径的最后一个字母
path.pop()
# 如果输入为空，返回空列表
if not digits:
return []
combinations = []
backtrack(0, [])
return combinations
执行：
总结
本文讨论的是一个经典的组合搜索问题：电话号码的字母组合。这类问题要求我们找到所有可能的组合方式，它们通常可以通过枚举所有可能性来解决，这正是回溯算法擅长的领域。
适用情境： 回溯算法适用于解决决策树的遍历问题。具体来说，这包括了组合问题（如本题）、排列问题、子集问题等。这类问题的特点是要求穷举所有可能的情况，而这些情况又可以通过一系列的选择和决策步骤来达成。电话号码的字母组合问题就是一个典型的组合问题，每按一次数字键，就相当于做了一次选择，所有选择的序列就构成了一个组合。
使用的算法： 本题使用的是回溯算法。回溯算法是一种通过递归来遍历解空间的搜索策略，它会尝试所有可能的分步方法，并在不满足条件时回溯上一步或几步，然后通过其他的可能的分步方法继续尝试寻找解。在本题中，我们首先为每个数字建立一个映射表来找出它可以代表的所有字母，然后递归地进行选择，每次选择一个字母，直到达到了数字串的长度。
算法流程：
- 建立一个映射表来关联数字和字母。
- 从输入的数字串的第一个数字开始，对于每个数字，遍历其对应的所有字母。
- 对于当前数字的每个字母，将其加到当前路径中，并递归地对剩余的数字进行同样的操作。
- 当路径的长度与数字串的长度相等时，将其加入到解集中。
- 如果路径不符合要求，或者已经加入到解集中，就回溯到上一个状态，尝试其他可能的路径。
这种方法高效地解决了问题，因为它避免了无效的搜索，并且在找到有效的字母组合后能够及时地回溯。通过递归实现的回溯算法非常适合解决这种需要枚举所有组合的问题，因为它能够简洁地表示决策过程，并在运行时动态地构建决策树。
总的来说，电话号码的字母组合问题是一个典型的回溯算法应用场景。通过学习这个问题的解法，我们不仅能够掌握如何使用回溯算法解决实际问题，还能够加深对递归思想和决策树搜索的理解，这对于提高编程能力和解决更复杂的算法问题都有很大的帮助。
