The first idea is the same backtracking as unique permutations, then drop duplicates with a set. Correct, but \(n \le 8\) and repeated numbers clone whole subtrees; filtering afterwards wastes time and space.
The bottleneck is those duplicate branches. Swapping two equal values at the same depth yields the same permutation — each value may be chosen only once per layer.
Sort so equals sit together, then skip a candidate when the previous equal is still unused. Each distinct value expands once at a position; every generated permutation is unique.
We can first sort the array so that duplicate numbers are placed together, making it easier to remove duplicates.
Then, we design a function \(\textit{dfs}(i)\), which represents the current number to be placed at the \(i\)-th position. The specific implementation of the function is as follows:
If \(i = n\), it means we have filled all positions, add the current permutation to the answer array, and then return.
Otherwise, we enumerate the number \(nums[j]\) for the \(i\)-th position, where the range of \(j\) is \([0, n - 1]\). We need to ensure that \(nums[j]\) has not been used and is different from the previously enumerated number to ensure that the current permutation is not duplicated. If the conditions are met, we can place \(nums[j]\) and continue to recursively fill the next position by calling \(\textit{dfs}(i + 1)\). After the recursive call ends, we need to mark \(nums[j]\) as unused to facilitate subsequent enumeration.
In the main function, we first sort the array, then call \(\textit{dfs}(0)\) to start filling from the 0th position, and finally return the answer array.
The time complexity is \(O(n \times n!)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array. We need to perform \(n!\) enumerations, and each enumeration requires \(O(n)\) time to check for duplicates. Additionally, we need a marker array to mark whether each position has been used, so the space complexity is \(O(n)\).
