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.
1import java.util.Arrays;
Java solution uses primitive swapping between indices to form permutations and relies on a Set for avoiding duplicates, allowing permutation logic to remain in-place and simple.