Every distinct ordering of numbers that may repeat. Sort first, then skip a copy whenever its twin to the left is still unused in this branch.
▼The problem
LeetCode 47 (Medium). Given a list of numbers that may contain duplicates, return all unique permutations.
Examples (LeetCode's): [1,1,2] → [[1,1,2],[1,2,1],[2,1,1]], [1,2,3] → all 6 permutations.
The solution
def permute_unique(nums):
nums.sort()
res, path = [], []
used = [False] * len(nums)
def back():
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
back()
path.pop()
used[i] = False
back()
return resTranscript
Permutations Two. Given numbers that may contain duplicates, return every ordering, but each one only once. It's Permutations plus Subsets Two's skip rule.
Take one, one, two. Just three line-ups: one one two, one two one, and two one one. One, two, three has no twins, so all six count.
The easy way: build all n factorial orderings, then drop repeats with a set. Swapping the two ones changes nothing, so one, one, two builds six to keep three. Eight ones? Over forty thousand built, one kept.
The key idea: sort first, so twins stand side by side. Fill the line slot by slot, marking each number used. Skip a number when it equals the one before it and that one is still unused. So twins go in order, and each line-up is built once.
In code: sort, then backtrack. When the path is full, save a copy. Otherwise try each number, skip used ones and waiting twins, mark the choice, recurse, then undo it.
Now one, one, two. Place the first one, then the second one, then two: one one two. Back up. Two, then the last one: one two one. At the start, the second one is skipped: its twin is unused. Two goes first, then both ones in order: two one one. Three line-ups, no repeats.
There can be n factorial line-ups, each copied in n steps: order n times n factorial time. The path and the used flags take order n space, plus the output.
Sort, keep twins in order, skip the waiting twin. That's Permutations Two.