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,1,2], [1,2,1], [2,1,1] ] Subscribe to see which companies asked this question.
public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> rst = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) return rst; List<Integer> res = new ArrayList<>(); boolean[] used = new boolean[nums.length]; Arrays.sort(nums); backtrace(nums, rst, res, used); return rst; } public void backtrace(int[] nums, List<List<Integer>> rst, List<Integer> res, boolean[] used) { if (res.size() == nums.length) { rst.add(new ArrayList<>(res)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; else if (i > 0 && nums[i] == nums[i-1] && used[i-1]) continue; else { used[i] = true; res.add(nums[i]); backtrace(nums, rst, res, used); used[i] = false; res.remove(res.size()-1); } } } }