Permutations II
Given a collection of numbers that may contain duplicates, return all possible unique permutations.
Open on LeetCode ↗Intuition
The tempting move is to reuse your Permutations I code, dump every result into a set, and return the set. It gives the right answer and it is the wrong solution. For [1,1,1,1,1,1] you generate 720 permutations and throw away 719 — you paid n! to keep one. The waste is exponential and it happens before the dedup ever runs, so no cleverness at the end can recover it. Attack the duplication where it is created instead: it comes from two equal values being swapped into the same slot at the same level of the tree, producing two identical subtrees. Sort the array first so equal values sit adjacent, then at each level skip nums[i] when nums[i] == nums[i-1] and the twin at i-1 is not currently in the path. That last clause is the subtle part — if the twin IS in the path, you are one level deeper and legitimately using the second copy. The invariant is that among identical values at a level, only the leftmost unused one is ever picked, so every distinct subtree is built exactly once and nothing is generated only to be discarded.
Sorting groups equal values together, and the skip condition nums[i] == nums[i-1] and not used[i-1] picks one canonical ordering among identical twins. The not used[i-1] part is the subtle half: it means the twin was already tried and undone at this level, so this subtree is a duplicate.
Approach
Sort so duplicates become neighbours
Without sorting, two equal values can be far apart and detecting a repeat needs a set or a counter. Sorting collapses that to a single comparison with the immediately preceding element, which is why almost every duplicate-skipping backtracking solution opens with a sort. It costs O(n log n) against an exponential body, so it is effectively free.
Skip a duplicate at the same tree level
Inside the loop, if i > 0 and nums[i] == nums[i-1] and used[i-1] is False, continue. Read the condition literally: the previous equal value is not in the current path, which means it was already tried in this same loop and its entire subtree is built. Picking nums[i] now would rebuild that subtree identically. When used[i-1] is True you are deeper in the tree and genuinely consuming a second copy, which is allowed.
Mark, recurse, unmark
The used array is what stops one index being consumed twice down a single path. Set used[i] before recursing and clear it after, alongside popping the value off the path. Both must be undone together — leaving used[i] set turns that index invisible to every sibling branch and silently truncates the answer.
Solution & live demo
Common pitfalls
Using used[i-1] instead of not used[i-1]
if i > 0 and nums[i] == nums[i-1] and used[i-1]:
continueif i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continueWhen the twin is used, it sits above on the current path and this element legitimately extends it — that's how [1,1,2] gets both 1s. The duplicate case is the twin being free, meaning its branch was already fully explored at this level.
Deduplicating the results afterwards
return [list(t) for t in set(map(tuple, res))]
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continueWith many repeats the tree generates factorially many duplicates before the set removes them — the work is done and thrown away. Pruning at the branch never enters those subtrees.
Skipping the sort
# no nums.sort()
nums.sort()
The duplicate check compares against the immediate left neighbour, which only identifies all twins when equal values are adjacent. Unsorted input leaves duplicates scattered and the prune misses most of them.
Edge cases
The skip fires on every duplicate at every level, so exactly one permutation is produced instead of n! identical ones.
The skip condition never triggers and the algorithm degrades gracefully into plain Permutations I, returning all n! results.
One level, one choice, one permutation — the loop runs once and the base case fires.
The initial sort brings them together, which is precisely why the sort cannot be skipped; without it the neighbour comparison misses the pair entirely.