import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
public class Solution {
// main method that takes in an integer array of unique numbers
public List<List<Integer>> permuteUnique(int[] nums) {
// create a list to store all permutations
List<List<Integer>> res = new ArrayList<List<Integer>>();
// sort the input array
Arrays.sort(nums);
// create a boolean array to keep track of used numbers
boolean[] used = new boolean[nums.length];
// create a list to store the current permutation
List<Integer> list = new ArrayList<Integer>();
// call dfs helper method
dfs(nums, used, list, res);
return res;
}
// dfs helper method
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res) {
// if the current permutation is the same length as the input array, add it to the result list
if (list.size() == nums.length) {
res.add(new ArrayList<Integer>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
// if the current number is used, skip it
if (used[i])
continue;
// if the current number is the same as the previous number and the previous number is not used, skip it
if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
continue;
// mark the current number as used
used[i] = true;
// add the current number to the current permutation
list.add(nums[i]);
// recursively call the dfs helper method
dfs(nums, used, list, res);
// mark the current number as not used
used[i] = false;
// remove the current number from the current permutation
list.remove(list.size() - 1);
}
}
// test cases
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = { 1, 2, 3 };
int[] nums2 = { 1, 1, 2 };
int[] nums3 = { 3, 3, 0, 3 };
System.out.println(solution.permuteUnique(nums1));
System.out.println(solution.permuteUnique(nums2));
System.out.println(solution.permuteUnique(nums3));
}
}