Leetcode 17. 电话号码的字母组合

心路历程：

之前看过这道题的解法但是忘了。一开始想多重循环遍历，发现不知道写几个for循环，于是想到递归；发现递归需要记录选择的路径而不是返回节点值，想到了回溯。
回溯的解题模板：维护两个变量，分别是候选集合和路径

注意的点：

1、这里边的候选集合是digits里的每一个数，而不是digits的一部分子集之类的。
2、返回条件是$i==n$而不是$i==n-1$，因为i为n-1时候选集合还有digits的最后一个元素
3、这个递归不能加cache装饰器

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits:return []maps = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'} n = len(digits)path = []res = []# 遍历digits中第i个数字def dfs(i):if i == n:res.append(''.join(path[:]))returnnum = int(digits[i])for c in maps[num]:path.append(c)dfs(i+1)path.pop()dfs(0)return res