力扣第 47 题
题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
相似问题：
分析
#1
0046 升级版，一种通用的的方法是将 nums 先排序，然后相同数只考虑第一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs():
if len(path) == len(nums):
res.append(path[:])
return
for i, x in enumerate(nums):
if x<inf and not (i and nums[i-1]==x):
nums[i]=inf
path.append(x)
dfs()
path.pop()
nums[i]=x
nums.sort()
res, path = [], []
dfs()
return res
|
7 ms
#2
还可以遍历计数器，相同的数也只会考虑一次。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs():
if len(path) == len(nums):
res.append(path[:])
return
for x in ct:
if ct[x]:
ct[x]-=1
path.append(x)
dfs()
path.pop()
ct[x]+=1
ct = Counter(nums)
res, path = [], []
dfs()
return res
|
7 ms