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.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class PermutationsUnique {
6 public List<List<Integer>> permuteUnique(int[] nums) {
7 List<List<Integer>> results = new ArrayList<>();
8 Arrays.sort(nums);
9 backtrack(nums, new boolean[nums.length], new ArrayList<>(), results);
10 return results;
11 }
12
13 private void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> results) {
14 if (current.size() == nums.length) {
15 results.add(new ArrayList<>(current));
16 return;
17 }
18 for (int i = 0; i < nums.length; i++) {
19 if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
20 continue;
21 }
22 used[i] = true;
23 current.add(nums[i]);
24 backtrack(nums, used, current, results);
25 used[i] = false;
26 current.remove(current.size() - 1);
27 }
28 }
29
30 public static void main(String[] args) {
31 PermutationsUnique pu = new PermutationsUnique();
32 System.out.println(pu.permuteUnique(new int[]{1, 1, 2}));
33 }
34}The Java solution implements a similar logic to the Python solution using arrays and lists for dynamic use checks and to form the permutation combinations.
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.
1function permuteUnique(nums) {
The JavaScript implementation suits series swapping along with converting array entries to strings for set storage, achieving uniqueness by reshaping results when retrieving.