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.
1function permuteUnique(nums) {
2 const results = [];
3 nums.sort((a, b) => a - b);
4 const backtrack = (combination, used) => {
5 if (combination.length === nums.length) {
6 results.push([...combination]);
7 return;
8 }
9 for (let i = 0; i < nums.length; i++) {
10 if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
11 continue;
12 }
13 used[i] = true;
14 combination.push(nums[i]);
15 backtrack(combination, used);
16 used[i] = false;
17 combination.pop();
18 }
19 };
20 backtrack([], Array(nums.length).fill(false));
21 return results;
22}
23
24console.log(permuteUnique([1, 1, 2]));This JavaScript function utilizes an array to keep track of which numbers have been used, ensuring that the output is a list of unique permutations by using sorting to manage duplicates.
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):
Implementing permutations through swapping allows the program to manage the sequence in-place and recursively form permutations, collecting results in a set for uniqueness.