回溯章节的典型17. 电话号码的字母组合。探究利用回溯解决字母的组合问题。
回溯的本质就是暴力算法，首先把映射字典related，路径path（也就是其中一个字母组合）以及总结果res写出来。

    def __init__(self):self.path = []self.res = []self.related = {'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”]

每一次，我们都选第一个数字digits[0] 进行处理，找出他的映射self.related[digits[0]进行遍历选择，然后递归调用它之后的数字。
例如，在示例中，我们选中2，得到映射abc，每一次我们将其中一个字母放进path中（以a为例），得到path = ['a']，然后递归self.combine(digits[1:])去处理3。

结束条件为传入的digits为空的时候，说明没有需要处理的数字了，此时我们将路径传入总结果res中。

总体代码如下：

class Solution:def __init__(self):self.path = []self.res = []self.related = {'1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}def combine(self, digits):if not digits:self.res.append(''.join(self.path))returnfor letter in self.related[digits[0]]:self.path.append(letter)self.combine(digits[1:])self.path.pop()def letterCombinations(self, digits: str) -> List[str]:if not digits: return []self.combine(digits)return self.res