- 分类:Backtracking
- 时间复杂度: O(n)
47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
代码:
方法:
class Solution:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res=[]
if nums==None or len(nums)==0:
return res
list_=[]
#加了这句用于去重
nums.sort()
visited=[False for i in range(len(nums))]
self.helper(res,visited,list_,nums)
return res
def helper(self,res,visited,list_,nums):
if len(list_)==len(nums):
res.append(list_.copy())
for i in range(len(nums)):
if (visited[i]):
continue
#加了这句用于去重
if (i>0 and nums[i]==nums[i-1] and (not visited[i-1])):
continue
list_.append(nums[i])
visited[i]=True
self.helper(res,visited,list_,nums)
visited[i]=False
list_.pop()
讨论:
和没有重复元素的 Permutation 一题相比,只加了两句话:
- Arrays.sort(nums) // 排序这样所有重复的数
- if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } // 跳过会造成重复的情况,没行过就不要行了!
网友评论