Permutation II

Question

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example For numbers [1,2,2] the unique permutations are:

[

    [1,2,2],

    [2,1,2],

    [2,2,1]

]

Challenge Do it without recursion.

Thoughts

与I类似

注意点

• 先sort()，将相同的element聚在一起
• 遇到用过的连续element就跳过

Solution

class Solution:
    """
    @param nums: A list of integers.
    @return: A list of unique permutations.
    """
    def permuteUnique(self, nums):
        # write your code here
        if not nums:
            return []
        self.resultList = []
        self.usedNum = {}
        self.nums = nums
        self.nums.sort()
        self.length = len(nums)
        self.permuteHelper([])
        return self.resultList

    def permuteHelper(self, curList):
        if len(curList) == self.length:
            newList = list(curList)
            self.resultList.append(newList)

        for idx, val in enumerate(self.nums):
            if idx != 0 and self.nums[idx-1] == val and self.usedNum[idx-1] == False:
                continue
            if idx in self.usedNum and self.usedNum[idx] == True:
                continue

            curList.append(val)
            self.usedNum[idx] = True
            self.permuteHelper(curList)
            curList.pop()
            self.usedNum[idx] = False