LeetCode【0047】全排列II

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\le nums.length\le 8$
• $-10\le nums[i]\le 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 题目总结

题目难度：中等
数据结构：数组
应用算法：回溯法