Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1 <= nums.length <= 8
-10 <= nums[i] <= 10
Solutions (Click to expand)
Similar to Permutations, we will use backtracking to recursively loop through and visit every non-visited members of the array to build a permutation. A Set will be used to record the indices already visited to make sure we don't insert a duplicate number. However, this time we will first sort the nums array and as we recursively loop through the array, we'll skip duplicate values when iterating by compare the current value with the very next value of the array. If the two values of the same we will skip it as recursively calling it will cause duplicate combinations in the our permutations array.
[[1 2 2 2 3 4], []]
[1 2 2 2 3 4]
^ ^ ^ ^ ^ ^
[1 2 2 2 3 4] // backtracking to 2, the very next value is the same, skip it
^ ^
[1 2 2 2 3 4] // the very next value is the same, skip it
^ ^
[1 2 2 2 3 4] // the next value is different, continue and recursively call it
^ ^
Time: O(N! * N) Where N is the total length of nums. Worst case with all unique numbers.
Space: O(N! * N)