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.
1def permuteUnique(nums):
2
Implementing permutations through swapping allows the program to manage the sequence in-place and recursively form permutations, collecting results in a set for uniqueness.