Permutations II

Generate all distinct permutations from a list that may contain duplicates.

permutations backtracking deduplication sorting

Given a list of integers `nums` that may contain duplicates, write a function `permuteUnique(nums)` that returns a list of all possible unique permutations. The order of the permutations in the output does not matter, but you must not include duplicate permutations. Each permutation should be a list of integers in the same order as they appear in the input. The function should be defined as:

def permuteUnique(nums):
    ...

The result must be a list of lists, where each inner list is one permutation. The input list can be empty.

Constraints

- `0 <= len(nums) <= 8`
- `-10 <= nums[i] <= 10`
- The number of unique permutations may be large but fits in memory for the given bounds.
- You may use any standard library, but not third-party packages.

Example

>>> permuteUnique([1,1,2])
[[1,1,2],[1,2,1],[2,1,1]]
>>> permuteUnique([1,2,3])
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
>>> permuteUnique([])
[[]]

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the input list first to bring duplicates together.

In each recursion, for each unused element, check if it is equal to the previous element and the previous element was not used in this position; if so, skip.

Use a used array to track visited indices during backtracking.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.