public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if (nums==null  nums.length==0) { return ans; }
permute(ans, nums, 0);
return ans;
}
private void permute(List<List<Integer>> ans, int[] nums, int index) {
if (index == nums.length) {
List<Integer> temp = new ArrayList<>();
for (int num: nums) { temp.add(num); }
ans.add(temp);
return;
}
Set<Integer> appeared = new HashSet<>();
for (int i=index; i<nums.length; ++i) {
if (appeared.add(nums[i])) {
swap(nums, index, i);
permute(ans, nums, index+1);
swap(nums, index, i);
}
}
}
private void swap(int[] nums, int i, int j) {
int save = nums[i];
nums[i] = nums[j];
nums[j] = save;
}
}
Share my Java code with detailed explanantion


Since we only need permutations of the array, the actual "content" does not change, we could find each permutation by swapping the elements in the array.
The idea is for each recursion level, swap the current element at 1st index with each element that comes after it (including itself). For example, permute[1,2,3]:
At recursion level 0, current element at 1st index is 1, there are 3 possibilities: [1] + permute[2,3], [2] + permute[1,3], [3] + permute[2,1].
Take "2+permute[1,3]" as the example at recursion level 0. At recursion level 1, current elemenet at 1st index is 1, there are 2 possibilities: [2,1] + permute[3], [2,3] + permute[1].
... and so on.
Let's look at another example, permute[1,2,3,4,1].
At recursion level 0, we have [1] + permute[2,3,4,1], [2] + permute[1,3,4,1], [3] + permute[2,1,4,1], [4] + permute[2,3,1,1], [1] + permute[2,3,4,1].
1 has already been at the 1st index of current recursion level, so the last possibility is redundant. We can use a hash set to mark which elements have been at the 1st index of current recursion level, so that if we meet the element again, we can just skip it.