Short Python Solution with explanation

• 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).

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