【原】LeetCode 17*/46*. 电话号码的字母组合/全排列（回溯法）（Python）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路：暴力破解，回溯法

利用树形结构如图 

将digits数组中每一位数字对应的字母依次取出来，再加上后面位置的数字所代表的的所有字母依次递归。。。

class Solution:

    res = []

    letterMap = {
        "0": " ",
        "1": "",
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

    def letterCombinations(self, digits: str) -> List[str]:
        # 一定要清除成员变量，否则下个测试用例中会有上一次的结果
        self.res = []

        if digits == "":
            return self.res
        self.findCombination(digits, 0, "")

        return self.res

    # s中保存此时从digits[0...index-1]数字组合中得到的一个字符串
    # 将digits[index]对应的字母添加到s中
    def findCombination(self, digits: str, index: int, s: str):
        if index == len(digits):
            self.res.append(s)
            return
        
        num = digits[index]
        letters = self.letterMap[num]
        for l in letters:
            self.findCombination(digits, index + 1, s + l)
        
        return

 这里使用了类的成员变量来存储最后的结果，注意一定要有 self.res = [] 这一步，否则leetcode上测试的前一个计算结果会保存下来影响后面的判断

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路：和第17题类似，都采用回溯法，代码整体框架不变，需要注意：

① 上一题中数字的顺序不变，例如[2, 3, 4]，最后的结果就是输出2，3，4所代表的字母的排列，而本题意思是结果中可能含有[4,3,2]......，所以数字顺序可变，因此需要另外一个数组used记录已经使用过的数字

② 使用回溯法时，递归出来之后要注意及时回复状态，例如从[1,2,3]出来，返回到[1,2,X]时，需要将3这个数字在used中重新记为未使用过，并将[1,2,3]变为[1,2]，此题更能体现回溯思想

python中深拷贝浅拷贝的问题。。。坑了我10分钟的时间调试

class Solution:

    res = []
    used = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.used = [0 for _ in nums]

        if len(nums) == 0:
            return []
        p = []
        self.generatePermutation(nums, 0, p)

        return self.res

    def generatePermutation(self, nums: List[int], index: int, p: List[int]):
        if index == len(nums):
            self.res.append(p.copy())   # 深复制，浅复制，好坑啊~~
            return
        
        for i in range(len(nums)):
            if self.used[i] == 0:
                p.append(nums[i])
                self.used[i] = 1
                self.generatePermutation(nums, index + 1, p)
                # 回溯到上一状态
                p.pop()
                self.used[i] = 0
        return