Short Python Solution with explanation

  • 0

    The idea to solve this problem builds up on the Permutations I problem, where each number n in nums was distinct. In that problem we could find permutations beginning with each number n_i and collect them all together to get all the permutations. Note, that permutation beginning with any number n_i would be different from the permutation beginning with another number n_j from nums, because n_i and n_j were distinct in that problem.

    In this problem, however, n_i and n_j need not be distinct. But if we use a set / hashmap to make a list of all distinct numbers and then find permutations beginning with each, then we can solve the problem in a similar fashion. Here is my Accepted solution for this problem (~72 percentile):

    class Solution(object):
        def permuteUnique(self, nums):
            if len(nums) <= 1:
                return [nums]
            # d will store index of the first occurrence of a number in nums
            d = {}
            for i, n in enumerate(nums):
                if n not in d:
                    d[n] = i
            l = []
            for n, i in d.iteritems():
                permutations = self.permuteUnique(nums[:i] + nums[i+1:])
                for p in permutations:
                    l.append([n] + p)
            return l

    dict is used instead of a set because along with the number n, I'd like to store it's index i, that will be used in slicing when calling permuteUnique recursively on a sub-list. (Also: This solution though simple to understand, isn't that great in terms of memory because a dict/hash-map is created for each recursive call).

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.