【Python】回溯之排列组合

电话号码的字母组合（leetcode 17）

思路：

• 构建哈希表进行数字和字母的映射
• 构建递归函数，需要回溯pop(path)
• 递归退出条件：当index越界，即遍历完digits列表时，退出递归，将当前path加入res
• 递归body：递归获取字符串，对字符串进行遍历，递归N层获取n个字符，当res.append(path)以后，再进行pop(path)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        dic = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        } 
        
        def backtrack(index: int):
            if index == len(digits):
                res.append("".join(path))
            else:
                digit = digits[index]
                for letter in dic[digit]:
                    path.append(letter)
                    backtrack(index + 1)
                    path.pop()

        path = []
        res = []
        backtrack(0)
        return res