> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/47-permutations-ii.md).

# 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

```python
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
```