Untitled

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // Sort first to group duplicates together
        Arrays.sort(nums);
        generatePermutations(0, nums, result);
        return result;
    }
    
    private void generatePermutations(int index, int[] nums, List<List<Integer>> result) {
        // When we reach the end, we've found a valid permutation
        if (index == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }
        
        // Track used numbers at current position to avoid duplicates
        HashSet<Integer> used = new HashSet<>();
        
        for (int i = index; i < nums.length; i++) {
            // If we've already used this number at current position, skip it
            if (used.contains(nums[i])) continue;
            
            // Add current number to used set for this position
            used.add(nums[i]);
            
            // Standard swap
            swap(nums, index, i);
            
            // Recurse for next position
            generatePermutations(index + 1, nums, result);
            
            // Backtrack: restore original order
            swap(nums, index, i);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        int[] nums = {1, 1, 2};
        System.out.println("Input: [1,1,2]");
        System.out.println("Output: " + solution.permuteUnique(nums));
        // Expected: [[1,1,2], [1,2,1], [2,1,1]]
    }
}