Permutations II (medium)

Problem Statement

Given a list of numbers nums that might have duplicates, return all unique arrangements of the numbers in any order.

Examples

Example 1:

Input: nums = [1, 2, 2]
Output: [[1,2,2],[2,1,2],[2,2,1]]
Explanation: There are a total of 6 permutations of [1, 2, 2] list but only 3 are unique.

Example 2:

Input: nums = [2, 2, 3]
Output: [[2,2,3],[2,3,2],[3,2,2]]
Explanation: All unique permutations of the list [2, 2, 3] are shown above.

Example 3:

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

.....

Like the course? Get enrolled and start learning!

Dakshesh Jain

· a year ago

This is perhaps a better solution since:

Uses hash-map to count frequency
Handles duplicate elements more effectively
Is slightly better in terms of time complexity (O(N!))

import collections

class Solution:
    def permuteUnique(self, nums):
        result = []
        
        freq = collections.Counter(nums) # can also use simple dict(or hash-map)

        def dfs(current_path):
            if len(current_path) == len(nums):
                result.append(list(current_path))
                return 

            for node in freq:
                if freq[node] == 0:
                    continue

                freq[node] -= 1
                current_path.append(node)

                dfs(current_path)

                freq[node] += 1
                current_path.p