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.
1using System;
2using System.Collections.Generic;
3
4class PermutationsUnique {
5 public IList<IList<int>> PermuteUnique(int[] nums) {
6 Array.Sort(nums);
7 var results = new List<IList<int>>();
8 Backtrack(nums, new bool[nums.Length], new List<int>(), results);
9 return results;
10 }
11
12 private void Backtrack(int[] nums, bool[] used, List<int> current, List<IList<int>> results) {
13 if (current.Count == nums.Length) {
14 results.Add(new List<int>(current));
15 return;
16 }
17 for (int i = 0; i < nums.Length; i++) {
18 if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
19 continue;
20 }
21 used[i] = true;
22 current.Add(nums[i]);
23 Backtrack(nums, used, current, results);
24 used[i] = false;
25 current.RemoveAt(current.Count - 1);
26 }
27 }
28
29 static void Main() {
30 var solution = new PermutationsUnique();
31 var result = solution.PermuteUnique(new[] { 1, 1, 2 });
32 foreach (var perm in result) {
33 Console.WriteLine(string.Join(",", perm));
34 }
35 }
36}The C# solution uses structure similar to the Java solution but uses C# collections. It employs sorting, a used tracker, and backtracking to manage duplicates effectively.
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.