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.
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
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.