47. Permutations II

Description

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

Solution

permutations-ii.py

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)

        def backtrack(mask, path):
            if len(path) == n:
                res.append(path)
                return

            for i in range(n):
                if mask & (1 << i) > 0: continue

                if i > 0 and nums[i] == nums[i - 1] and mask & (1 << (i - 1)) > 0: continue

                backtrack(mask | (1 << i), path + [nums[i]])

        backtrack(0, [])
        return res