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