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

Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Explanation: Even though 1 appears twice, the three unique permutations are returned. Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Sort the array first so duplicate values are adjacent. When iterating candidates for a position, skip a candidate if it equals the previous candidate and the previous candidate was not used in the current path (meaning we are at the same level of the tree and would create a duplicate branch).

import java.util.*; class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(nums, used, new ArrayList<>(), result); return result; } private void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) { if (current.size() == nums.length) { result.add(new ArrayList<>(current)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // Skip duplicate at same tree level if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; current.add(nums[i]); backtrack(nums, used, current, result); current.remove(current.size() - 1); used[i] = false; } } }
Complexity Analysis:

Time complexity: O(n * n!) worst case (all distinct). Fewer with duplicates due to pruning.
Space complexity: O(n) recursion depth.