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.
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.