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.
1using System;
2using System.Collections.Generic;
3
4class PermutationsUniqueSwapSet {
public IList<IList<int>> PermuteUnique(int[] nums) {
var results = new HashSet<string>();
Permute(nums, 0, results);
var listResults = new List<IList<int>>();
foreach(var res in results) {
var lst = new List<int>();
foreach(var c in res.Split(',')) {
lst.Add(int.Parse(c));
}
listResults.Add(lst);
}
return listResults;
}
private void Permute(int[] nums, int start, HashSet<string> results) {
if (start == nums.Length) {
results.Add(string.Join(",", nums));
return;
}
for (int i = start; i < nums.Length; i++) {
Swap(nums, start, i);
Permute(nums, start + 1, results);
Swap(nums, start, i);
}
}
private void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
static void Main() {
var solution = new PermutationsUniqueSwapSet();
var result = solution.PermuteUnique(new[] { 1, 1, 2 });
foreach (var perm in result) {
Console.WriteLine(string.Join(",", perm));
}
}
}The C# solution embraces swapping while using a HashSet to collect unique permutations by leveraging string representations of the permutations.