Untitled
unknown
plain_text
2 months ago
2.2 kB
3
Indexable
import java.util.*; class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> result = new ArrayList<>(); // First sort the array to handle duplicates effectively Arrays.sort(nums); 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) { // When current permutation is complete, add it to result if (current.size() == nums.length) { result.add(new ArrayList<>(current)); return; } // Try each number as the next element in the permutation for (int i = 0; i < nums.length; i++) { // Skip if the number is already used in current permutation if (used[i]) continue; // Skip duplicates to avoid generating same permutations // We only want to use same number again if its previous occurrence was used if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // Include current number in permutation used[i] = true; current.add(nums[i]); // Recursively generate remaining permutation backtrack(nums, used, current, result); // Backtrack: remove current number to try next possibility used[i] = false; current.remove(current.size() - 1); } } public static void main(String[] args) { Solution solution = new Solution(); // Test cases int[] nums1 = {1, 1, 2}; System.out.println("Input: [1,1,2]"); System.out.println("Output: " + solution.permuteUnique(nums1)); // Expected output: [[1,1,2], [1,2,1], [2,1,1]] int[] nums2 = {1, 2, 2}; System.out.println("\nInput: [1,2,2]"); System.out.println("Output: " + solution.permuteUnique(nums2)); // Expected output: [[1,2,2], [2,1,2], [2,2,1]] } }
Editor is loading...
Leave a Comment