# 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