LeetCode【0047】全排列II
本文目录
- 1 中文题目
- 2 求解方法:回溯法
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
- 3 题目总结
1 中文题目
给定一个可包含重复数字的序列 nums
,按任意顺序
返回所有不重复的全排列。
示例:
输入: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]]
提示:
- 1 ≤ n u m s . l e n g t h ≤ 8 1 \leq nums.length \leq 8 1≤nums.length≤8
- − 10 ≤ n u m s [ i ] ≤ 10 -10 \leq nums[i] \leq 10 −10≤nums[i]≤10
2 求解方法:回溯法
2.1 方法思路
方法核心
通过回溯法实现所有可能的排列,使用交换元素的方式进行排列生成,在每一层递归中使用集合记录已经使用过的数字来避免重复,同时通过预先排序来确保相同数字的相对位置固定,从而保证不会生成重复的排列。
实现步骤
(1)预处理阶段:
- 对输入数组进行排序,使相同的数字相邻
- 初始化结果列表用于存储所有合法排列
- 获取输入数组的长度
(2)回溯函数设计:
- 定义参数first表示当前要填充的位置
- 在每一层递归中维护一个used集合记录已使用的数字
- 通过交换元素的方式生成不同的排列
- 使用集合去重来避免同一层使用相同的数字
(3)去重策略:
- 在每一层递归中使用集合记录已经在该位置使用过的数字
- 如果某个数字在当前层已经使用过,则跳过
- 通过预排序确保相同数字的相对顺序不变
(4)状态恢复:
- 在递归返回前将交换的元素换回原位
- 保证不影响后续的排列生成
方法示例
以输入 nums = [1,1,2] 为例:
初始状态:
nums = [1,1,2](已排序)
result = []递归过程详解:1. first = 0:used = set()1.1 i = 0: nums[0] = 1used = {1}交换后:[1,1,2]递归到first = 11.1.1 used = set()i = 1: nums[1] = 1used = {1}交换后:[1,1,2]递归到first = 21.1.1.1 used = set()i = 2: nums[2] = 2used = {2}交换后:[1,1,2]递归到first = 3添加排列[1,1,2]恢复:[1,1,2]恢复:[1,1,2]恢复:[1,1,2]1.2 i = 1: nums[1] = 11在used中,跳过1.3 i = 2: nums[2] = 2used = {1,2}交换后:[2,1,1]递归到first = 1... (类似过程)最终添加排列[2,1,1]恢复:[1,1,2]最终结果:
result = [[1,1,2], [1,2,1], [2,1,1]]
2.2 Python代码
class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:# 结果列表result = []n = len(nums)# 先对数组排序,方便后续去重nums.sort()def backtrack(first = 0):# 如果已经到达数组末尾,说明找到了一个排列if first == n:result.append(nums[:])return# 用于记录当前层使用过的数字used = set()# 尝试将每个数字放到当前位置for i in range(first, n):# 如果当前数字已经在当前层使用过,则跳过if nums[i] in used:continue# 将当前数字加入已使用集合used.add(nums[i])# 交换当前数字到待填充位置nums[first], nums[i] = nums[i], nums[first]# 递归处理下一个位置backtrack(first + 1)# 回溯,恢复原状nums[first], nums[i] = nums[i], nums[first]# 开始回溯backtrack()return result
2.3 复杂度分析
- 时间复杂度:O(n!)
- 对于n个不同的数字,有n!种排列
- 对于有重复数字的情况,排列数会少于n!
- 每个排列需要O(n)的时间来复制到结果集
- 排序需要O(nlogn)的时间,但这不是主导项
- 空间复杂度:O(n)
- 递归调用栈的深度为O(n)
- 每层递归中的used集合大小最大为O(n)
3 题目总结
题目难度:中等
数据结构:数组
应用算法:回溯法