Medium

Permutations II

LAB

Return all unique permutations of nums sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    1,
    2
  ]
}

Output
[
  [
    1,
    1,
    2
  ],
  [
    1,
    2,
    1
  ],
  [
    2,
    1,
    1
  ]
]

FUNCTION SHAPE

nums: intArray→intMatrix

SOLUTION NOTE

You know the drill. Same as Permutations but with a set to handle duplicates.

Reveal reference solution +

pythonREFERENCE

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res = set()

    # swap
    def backtrack(i):
        if i == n:
            res.add(tuple(nums))
        else:
            for j in range(i, n):
                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i+1)  # has to be i+1, NOT j+1 !!!
                nums[i], nums[j] = nums[j], nums[i]

    backtrack(0)
    return list(res)

# Alternative
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    return list(set(tuple(A) for A in permute(nums)))

TimeO(n*n!)

SpaceO(n*n!)

Open on LeetCode ↗