Permutations II from leetcode solution

Question

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

For example, [1,1,2] have the following unique permutations: [[1,1,2], [1,2,1], [2,1,1]]

There are many better solutions out there but I am interested in just the code review and how it can be made better.

Solution is exactly described here

Let's use input abc as an example.

Start off with just the last element (c) in a set (["c"]), then add the second last element (b) to its front, end and every possible positions in the middle, making it ["bc", "cb"] and then in the same manner it will add the next element from the back (a) to each string in the set making it:

"a" + "bc" = ["abc", "bac", "bca"] and "a" + "cb" = ["acb" ,"cab", "cba"] Thus entire permutation:

["abc", "bac", "bca","acb" ,"cab", "cba"]

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums or len(nums) == 1:
            return [nums]
        output_list, output_list_copy, temp_output = [], [], []
        for num in nums:
            if not output_list:
                output_list = [[num]]
                continue
            for t in output_list:
                assigned, already_seen = False, None
                for j in range(len(t)+1):
                    if already_seen == num and assigned:
                        continue
                    t1 = t[0:j] + [num] + t[j:]
                    if j < len(t) and t[j] == num:
                        assigned, already_seen = True, num
                    temp_output.append(t1)
                output_list_copy += temp_output
                temp_output = []
            output_list = output_list_copy
            output_list_copy = []
        return output_list

Answer 1

I have a few pointers,

• Use libraries when possible, you are currently reinventing the wheel of itertools.permutations

• You could use a set() to have \$O(N)\$ lookup when finding items that are already seen.

• You should use generators instead of keeping everything in a list, this avoids high memory usage when working with large numbers

Reinventing the wheel

class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        def unique_perms(elements, unique):
            if len(elements) <=1:
                yield elements
            else:
                for perm in unique_perms(elements[1:], unique):
                    for i in range(len(elements)):
                        next_perm = perm[:i] + elements[0:1] + perm[i:]
                        if tuple(next_perm) not in unique:
                            unique.add(tuple(next_perm))
                            yield next_perm

        return list(unique_perms(nums, set()))

Using modules

from itertools import permutations

def permute_unqiue(nums, r):
    return list(set(permutations(nums, r)))

This works by making a set() of the permutations. That removes all duplicate values, since they will hash to the same thing. Afterwards you can return the list() of unique permutations.

Answer 2

Ludusposed's answer is excellent but it can still be improved. Indeed, you don't need a class.