Permutations II
mediumTime: O(n * n!)Space: O(n)
Recognize the pattern
all unique permutations from array with duplicatesskip same-value at same levelsort + used array
Brute force idea
Generate all, deduplicate — O(n! × n).
Better approach
Sort. Backtrack with used array. Skip nums[i] if nums[i] == nums[i-1] and !used[i-1]. O(n! / duplicates).
Key invariant
Identical values are forced into left-to-right usage order — prevents generating the same permutation via different copies.
Watch out for
The skip condition: skip if nums[i] == nums[i-1] AND !used[i-1]. This forces identical values to be used in order.