47 Permutations II
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]
]
The Idea: The key is to identify when the next duplicate will take place. I think it is best illustrated through an example. Suppose that our current set of new unique permutations are:
[[123,4,3,123], [4,123,3,123], [4,3,123,123]], and that the algorithm added the number 123 after index 1 into the array [4,3,123]. The next iteration would append 123 to the right of index 2 in [4,3,123], which would identify as a duplicate.Complexity: O(n!) time (worse case - no duplicates), and O(1) space
class Solution:
def permuteUnique(self, nums):
sol = [[]]
for n in nums:
next_sol = []
for prev in sol:
# ab, ba
for i in range(0, len(prev) + 1):
# cab, acb, abc
next_sol.append(prev[:i] + [n] + prev[i:])
# this line identifies duplicates
if i < len(prev) and prev[i] == n:
break
sol = next_sol
return sol
Last modified 4yr ago