Hot100——回溯

全排列

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums中的所有整数互不相同

dfs回溯

注意：res在添加的时候是res.append(path[:])，res.append(path)这个是传递本质上是复制了path的地址，但是每次dfs结束后path会变为空的，所以直接那么写最后会返回空列表。所以写成res.append(path[:]) 做一次浅拷贝即可。（或者写成res.append(path.copy())）

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def dfs(nums, size, depth, path, flag, res): if depth == size: res.append(path[:]) return for i in range(size): if not flag[i]: path.append(nums[i]) flag[i] = True dfs(nums, size, depth + 1, path, flag, res) flag[i] = False path.pop() size = len(nums) if size == 0: return [] res = [] flag = [False for _ in range(size)] dfs(nums, size, 0, [], flag, res) return res

dfs回溯优化—去掉标记数组

用一个first来维护已选数字和未选数字。

官方思路：

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: result = [] path=list() def dfs(first:int): if first==len(nums): result.append(path.copy()) return for i in range(first,len(nums)): path.append(nums[i]) nums[first] ,nums[i]= nums[i],nums[first] dfs(first+1) path.pop() nums[first] ,nums[i]= nums[i],nums[first] dfs(0) return result

子集

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums中的所有元素互不相同

python自带函数库

itertools.combinations(iterable, r)这个就是生成组合数的库，iterable是迭代对象，r是从迭代对象中选出r个数进行组合。（组合的特点：

• 组合是无序的：选取的元素顺序和原可迭代对象中一致，且不重复选取同一元素、不考虑排列顺序（比如从[1,2]中取 2 个元素，只会生成(1,2)，不会再生成(2,1)）；
• 无重复组合：每个组合中的元素都是唯一的（基于原可迭代对象的元素位置，而非值，若原对象有重复值，会生成重复组合，但本题中nums是无重复元素的）

）

itertools.permutations(iterable, r)：生成的是排列，考虑顺序（比如从[1,2]取 2 个元素，会生成(1,2)和(2,1)）

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums) + 1): tmp = itertools.combinations(nums, i) #tmp是元组 res = res + list(tmp) #tmp转换为列表 return res

迭代

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [[]] for i in nums: res = res + [[i] + num for num in res] return res

递归

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] n = len(nums) def dfs(i, tmp): res.append(tmp) for j in range(i, n): dfs(j + 1, tmp + [nums[j]]) dfs(0, []) return res

电话号码的字母组合

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

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

示例 1：

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

示例 2：

输入：digits = "2"输出：["a","b","c"]

提示：

• 1 <= digits.length <= 4
• digits[i]是范围['2', '9']的一个数字。

回溯

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