# LC 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

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

This is very similar to permutation I, where we need to use backtracking to find all solutions. But in permutation II. We need to remove all duplicate.

where do dulicates come from

Let’s use the given example to build the tree where each leaf node is the a permutation.

At each level i of this tree, we are essentially building the permutation by choosing a number to insert into the ith position in the permutation. So at level 1, we want to choose a number from the input to fill the 1 digit of the permutation.

We can see the leaf nodes contain duplicates. This is caused by duplicate internal nodes. These internal duplicate nodes are there because we pick the same number, from different places in the input array, to append to our solution.
For example, given input [1,1,2] The first level are 1, 1 and [2]. 1 and 1 are duplicate from input[0] and input1.
In the next level, the input for both internal nodes1 will be [1,2] so their subtree will be the same.

To keep the tree duplicate free, we want to make sure the internal nodes at each level are all unique.

In our recursive function, we recursive only if the previous number is different from the current number.

``````class Solution:
def __init__(self):
self.sol = []
def permuteUnique(self, nums: 'List[int]') -> 'List[List[int]]':
def recur(path, nums):
if not nums:
self.sol.append(path)
return
for i in range(len(nums)):
if i > 0 and nums[i - 1] == nums[i]: continue  #if duplicate, skip.
recur(path + [nums[i]], nums[:i] + nums[i + 1:])
nums.sort()  #have to sort the input, else this algorithm will fail
recur([], nums)
return self.sol
``````