Question Given a collection of numbers, nums
, that might contain duplicates, return all possible unique permutations in any order .
https://leetcode.com/problems/permutations-ii/
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 public List<List<Integer>> permuteUnique(int [] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, new boolean [nums.length]); return list; } private void backtrack (List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used) { if (tempList.size() == nums.length){ list.add(new ArrayList<>(tempList)); } else { for (int i = 0 ; i < nums.length; i++){ if (used[i] || i > 0 && nums[i] == nums[i-1 ] && !used[i - 1 ]) continue ; used[i] = true ; tempList.add(nums[i]); backtrack(list, tempList, nums, used); used[i] = false ; tempList.remove(tempList.size() - 1 ); } } }
Complexity:
Time complexity: O(N!)
Space complexity: O(n)