forked from gavinfish/leetcode-share
-
Notifications
You must be signed in to change notification settings - Fork 0
/
047 Permutations II.py
33 lines (28 loc) · 970 Bytes
/
047 Permutations II.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
'''
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
nums.sort()
self.get_permute([], nums, result)
return result
def get_permute(self, current, num, result):
if not num:
result.append(current + [])
return
for i, v in enumerate(num):
if i - 1 >= 0 and num[i] == num[i - 1]:
continue
current.append(num[i])
self.get_permute(current, num[:i] + num[i + 1:], result)
current.pop()
if __name__ == "__main__":
assert Solution().permuteUnique([1, 2, 1]) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]