## Description

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

Given a collection of numbers, `nums`

, that might contain duplicates, return *all possible unique permutations in any order.*

**Example 1:**

Input:nums = [1,1,2]Output:[[1,1,2], [1,2,1], [2,1,1]]

**Example 2:**

Input:nums = [1,2,3]Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**Constraints:**

`1 <= nums.length <= 8`

`-10 <= nums[i] <= 10`

## Explanation

Backtracking to find permutations. The difference between this Permutations II and Permutation is that this problem has duplicate values. So we should skip the element by position not by value when building permutations. Also if the permutation has been found, we don’t need to add them to the final result list.

## Python Solution

```
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
results = []
nums = sorted(nums)
visited = set()
self.helper(results, nums, [], 0, visited)
return results
def helper(self, results, nums, permutation, start, visited):
if len(permutation) == len(nums) and permutation not in results:
results.append(list(permutation))
return
for i in range(len(nums)):
if i in visited:
continue
visited.add(i)
permutation.append(nums[i])
self.helper(results, nums, permutation, start, visited)
permutation.pop()
visited.remove(i)
```

- Time Complexity: O(N).
- Space Complexity: O(N).