Sponsored
Sponsored
This approach uses backtracking to generate permutations and a boolean array to track used elements in the current permutation combination. By sorting the array at the start, we can easily skip duplicates.
Time Complexity: O(n * n!) due to the generation of all permutations.
Space Complexity: O(n!) for storing the permutations and O(n) for the recursion stack.
1def permuteUnique(nums):
2 def backtrack(combination, used):
3 if len(combination) == len(nums):
4 results.append(list(combination))
5 return
6
7 for i in range(len(nums)):
8 if used[i] or i > 0 and nums[i] == nums[i-1] and not used[i-1]:
9 continue
10 used[i] = True
11 combination.append(nums[i])
12 backtrack(combination, used)
13 used[i] = False
14 combination.pop()
15
16 results = []
17 nums.sort()
18 backtrack([], [False] * len(nums))
19 return results
20
21print(permuteUnique([1, 1, 2]))This Python solution uses recursion and backtracking to generate permutations. Sorting the nums list initially helps to efficiently skip duplicates by checking if the element is the same as the previous one and if the previous one has been used.
This method carries out permutations by recursively swapping elements and employs a set to track unique permutations and avoid generating duplicate results. It does not require sorting initially but uses swaps directly to generate permutations.
Time Complexity: O(n * n!)
Space Complexity: O(n * n!) because of the set used to store permutations.
1function permuteUnique(nums) {
The JavaScript implementation suits series swapping along with converting array entries to strings for set storage, achieving uniqueness by reshaping results when retrieving.