Given an array nums that may contain duplicates, return all distinct permutations of it. Two orderings that look the same must appear only once. You may return them in any order.
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force runs the normal permutation algorithm and removes duplicates with a set, which can waste a lot of work (for [1,1,1,1,1,1,1,2], 40320 orderings give only 8 distinct ones). Duplicates come from placing two equal values in the same slot in different branches. After sorting, equal values are adjacent, and we add one rule: among equal values, always use them left to right. So nums[i] may only be chosen if the equal value before it, nums[i - 1], is already in the path. Each distinct permutation is then built exactly once.
Algorithm
- Sort
numsand createused,pathandres. - If
pathhas lengthn, record a copy. - For each
i: skip ifused[i]. - Also skip if
i > 0,nums[i] == nums[i - 1]andused[i - 1]is false. - Otherwise choose
nums[i], recurse, then undo the choice.
O(n * n!) in the worst case (all distinct)Space: O(n) for recursion and `used`, plus the output!used[i - 1] is the subtle part. Explain it as "a duplicate can only be used after its twin on the left", which interviewers find convincing. Using a per-level hash set of values tried at this slot is an easier to explain alternative.class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() # equal values become neighbours n = len(nums) res, path = [], [] used = [False] * nΒ def backtrack(): if len(path) == n: res.append(path[:]) return for i in range(n): if used[i]: continue # Use equal values left to right only: skip if the twin on the left is not in the path. if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(nums[i]) backtrack() path.pop() used[i] = FalseΒ backtrack() return res