6/25/2017 - 9:31 AM

## 47. Permutations II

1. Permutations II
``````class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.nums = sorted(nums)
self.res = []
self.cur = []
self.isVisited = [0] * len(nums)
self.backtracking()
return self.res
def backtracking(self):
if len(self.cur) == len(self.nums):
self.res.append([each for each in self.cur])
return
preNum = float('inf')
# Use preNum to prevent duplicates
for i in range(len(self.nums)):
# Update both self.isVisited and self.cur
if self.isVisited[i] == False:
if preNum == self.nums[i]:
continue
self.isVisited[i] = True
curNum = self.nums[i]
self.cur.append(curNum)
self.backtracking()
del self.cur[-1]
self.isVisited[i] = False
preNum = self.nums[i]``````

https://leetcode.com/problems/permutations-ii/#/description

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]
]
``````