ms/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4018,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:Te55,

Problem

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Examples

Example 1

Input: nums = [3,2,3]
Output: 3

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution

Method 1 - Backtracking with frequency map

This is similar to Permutations of Array 1. But the normal decision tree will not work.

permutations-of-arr-2-wrong-way-sst.excalidraw

So, instead of array, we can use hashmap of frequency. This is our frequency map:

freq<num,count> = {1: 1, 2:1}

Now, decision tree will have 2 keys - [1, 2]. On the left side, we choose one 1 and one 2.

Final decision tree:

permutations-of-arr-2-sst.excalidraw.excalidraw

Code

[{"language":"Java","code":"public List<List<Integer>> permuteUnique(int[] nums) {\n\tList<List<Integer>> ans = new ArrayList<>();\n\tList<Integer> subAns = new ArrayList<>();\n\t// frequency map\n\tMap<Integer, Long> countMap = Arrays.stream(nums).boxed().\n                collect(Collectors.groupingBy(Integer::intValue, Collectors.counting()));\n\n\tdfs(nums.length, countMap, subAns, ans);\n\treturn ans;\n}\n\npublic void dfs(int numsLength, Map<Integer, Long> countMap, List<Integer> subAns, List<List<Integer>> ans) {\n\tif (subAns.size() == numsLength) {\n\t\tans.add(new ArrayList<>(subAns));\n\t\treturn;\n\t}\n\tfor(int num: countMap.keySet()){\n\t\tif(countMap.get(num) > 0){\n\t\t\tsubAns.add(num);\n\t\t\tcountMap.put(num, countMap.get(num)-1);\n\n\t\t\tdfs(numsLength, countMap, subAns, ans);\n\n\t\t\t// undo\n\t\t\tcountMap.put(num, countMap.get(num)+1);\n\t\t\tsubAns.remove(subAns.size()-1);\n\t\t}\n\t}\n}","lang":"java"}]

Complexity

⏰ Time complexity: O(n*2^n)
🧺 Space complexity: O(n) assuming recursion stack

Method 2 - Backtracking with visited array and sorting

Code

[{"language":"Java","code":"public List<List<Integer>> permuteUnique(int[] nums) {\n\tList<List<Integer>> list = new ArrayList<>();\n\tArrays.sort(nums);\n\tbacktrack(list, new ArrayList<>(), nums, new boolean[nums.length]);\n\treturn list;\n}\n\nprivate v

Related Tags