Untitled
unknown
plain_text
2 months ago
1.9 kB
4
Indexable
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]] } }
Editor is loading...
Leave a Comment