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.
enter image description here

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

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax