Permutations II
mediumTime: O(n * n!)Space: O(n)
Signals to notice
all unique permutations from array with duplicatesskip same-value at same levelsort + used array
Brute force first
Generate all, deduplicate — O(n! × n).
The key insight
Sort. Backtrack with used array. Skip nums[i] if nums[i] == nums[i-1] and !used[i-1]. O(n! / duplicates).
What must stay true
Identical values are forced into left-to-right usage order — prevents generating the same permutation via different copies.
Easy way to go wrong
The skip condition: skip if nums[i] == nums[i-1] AND !used[i-1]. This forces identical values to be used in order.