47. Permutations II (全排列有重复的元素)

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],
  [2,1,1]
]


与上一题不同，就是在19行加个判断即可。

 1 class Solution(object):
 2     def __init__(self):
 3         self.res = []
 4 
 5     def permuteUnique(self, nums):
 6         """
 7         :type nums: List[int]
 8         :rtype: List[List[int]]
 9         """
10         self.help(nums, 0, len(nums))
11 
12         return self.res
13 
14     def help(self, a, lo, hi):
15         if(lo == hi):
16             self.res.append(a[0:hi])
17         for i in range(lo, hi):
18             #判断 i 是否已经在当过头元素了
19             if a[i] not in a[lo:i]:
20                 self.swap(a, i, lo)
21                 self.help(a, lo + 1, hi)
22                 self.swap(a, i, lo)
23     def swap(self, a, i, j):
24         temp = a[i]
25         a[i] = a[j]
26         a[j] = temp