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