Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Examples
Input: nums = [1,1,2] Output:[[1,1,2], [1,2,1], [2,1,1]]
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints
Java Solution (Backtracking)
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<Integer>();
boolean[] used = new boolean[nums.length];
backtrack(result, current, nums, used);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] used) {
if(current.size() == nums.length) result.add(new ArrayList<Integer>(current));
else{
for(int i = 0; i < nums.length; i++) {
if(used[i] || ( i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
continue;
current.add(nums[i]);
used[i] = true;
backtrack(result, current, nums, used);
used[i] = false;
current.remove(current.size() - 1);
}
}
}
}