典型回溯题目 - 全排列（一、二）

典型回溯题目 - 全排列（一、二）

46. 全排列

题目链接：46. 全排列状
题目大意：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

注意：（1）1 <= nums.length <= 6；（2）-10 <= nums[i] <= 10；（3）nums 中的所有整数 互不相同。

提示：LC的灵佬的视频题解非常好，下面的图片截取自对应视频。

示例：

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

参考代码：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:# return list(set(itertools.permutations(nums, len(nums))))def dfs(i):if i==n:ans.append(path.copy())return for j in range(n):if not on_path[j]:path[i] = nums[j]on_path[j] = Truedfs(i+1)on_path[j] = Falsen = len(nums)ans = []path = [0]*non_path = [False]*ndfs(0)return ans

• 时间复杂度：$O(n\times n!)$，其中 n 为数组 nums 的长度，该推论可见灵佬的视频。
• 空间复杂度：$O(n)$

47. 全排列 II

题目链接：47. 全排列 II
题目大意：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

注意：（1）1 <= nums.length <= 8；（2）-10 <= nums[i] <= 10。

提示：在全排列的基础上进行条件束缚，进行去重操作。

示例：

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

参考代码：

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:# return list(set(itertools.permutations(nums, len(nums))))nums.sort()  def dfs(i):if i==n:ans.append(path.copy())return for j in range(n):if not on_path[j]:if j>0 and nums[j]==nums[j-1] and not on_path[j-1]:continuepath[i] = nums[j]on_path[j] = Truedfs(i+1)on_path[j] = Falsen = len(nums)ans = []path = [0]*non_path = [False]*ndfs(0)return ans

• 时间复杂度：$O(n\times n!)$，其中 n 为数组 nums 的长度。
• 空间复杂度：$O(n)$

小结

这两道题是非常经典的回溯问题，很值得反复学习记忆。