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
itertools.permutations
? \$\endgroup\$