给定一个仅包含数字 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
这里使用了类的成员变量来存储最后的结果，注意一定要有 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]，此题更能体现回溯思想
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
