Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
1 2 3 4 5
| [ [1,1,2], [1,2,1], [2,1,1] ]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); permutation(result, new ArrayList<Integer>(), nums, new boolean[nums.length]); return result; } public void permutation(List<List<Integer>> result, ArrayList<Integer> cur, int[] nums, boolean[] used) { if (cur.size() == nums.length) { result.add(new ArrayList<Integer>(cur)); } else { for (int i = 0; i < nums.length; i++) { if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue; cur.add(nums[i]); used[i] = true; permutation(result, cur, nums, used); cur.remove(cur.size() - 1); used[i] = false; } } } }
|