Description
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example
1 2 3 4 5 6 7
| Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
|
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); if (nums == null || nums.length == 0) return res; Arrays.sort(nums); boolean[] visited = new boolean[nums.length]; helper(nums, res, new ArrayList<>(), visited); return res; } private void helper(int[] nums, List<List<Integer>> res, List<Integer> cur, boolean[] visited){ if (cur.size() == nums.length){ res.add(new ArrayList<>(cur)); return; } for (int i = 0; i < nums.length; i++){ if (visited[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue; cur.add(nums[i]); visited[i] = true; helper(nums, res, cur, visited); visited[i] = false; cur.remove(cur.size() - 1); } } }
|