[LeetCode] 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Thought process:
If the collection contains duplicate, I cannot only use the original method I used in "46. Permutations", because it will produce duplicate permutations. For example, if the collection is [0, 1, 1], the result will contain two [0, 1, 1]s.
The idea is to maintain a rule about which one of the duplicate numbers can appear in the permutations. To do this, I can sort the array and make sure that only the number with a smaller index can appear in a duplicate permutation.
For example, as I add numbers to the permutation list, if I found that I'm adding the second 1 while the first 1 is not in the list, that means the first 1 has already been used to make the exact same permutation. So I continue to the next iteration.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> permutations = new ArrayList<>(); List<Integer> permutation = new ArrayList<>(); boolean[] visited = new boolean[nums.length]; Arrays.sort(nums); permuteUnique(nums, permutation, visited, permutations); return permutations; } private void permuteUnique(int[] nums, List<Integer> permutation, boolean[] visited, List<List<Integer>> permutations) { if (permutation.size() == nums.length) { permutations.add(new ArrayList<>(permutation)); } for (int i = 0; i < nums.length; i++) { if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) { continue; } visited[i] = true; permutation.add(nums[i]); permuteUnique(nums, permutation, visited, permutations); permutation.remove(permutation.size() - 1); visited[i] = false; } } }

Time complexity: O(n! * n).