## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Permutations II

Sharing is caring!

Problem statement
Given a list, `nums`, of distinct numbers, return all possible unique permutations.

Sample input

```[1,2,1]
```

Sample output

```[[1, 2, 1], [2, 1, 1], [1, 1, 2]]
```

Solution
In another post we showed how this problem can be solved iteratively.

We can use the same technique but add a check to skip adding the number `n` to any subsequent positions of a list if we stumble upon a duplicate.

Let `nums = [1,2,1]`. And let `ans = [[]]`. The first number is `1` and the first list in `ans` is `[]`. We then make a copy of `[]` and add `1` at every position in `[]` which results in ``. We add the newly created list to our new answer list and replace `ans` with that and repeat. The next number is `2`. We then iterate over `ans` and add `2` at every possible position in every list we iterate over in `ans`. The only list in `ans` is ``. So we make a copy and add `2` at position `0` and then make another copy and add `2` at position `1`. We add the resulting lists to our new answer list and replace `ans` with that list, resulting in `ans = [[2,1], [1,2]]`. The next number in `nums` is `1`. Again, we then iterate over `ans` (`[[2,1], [1,2]]`) and add `1` at every possible position in every list in `ans`. So for list `[2,1]` in `ans` we get `[1,2,1]` for position `0` and `[2,1,1]` for position `1`. We then see that we just added `1` at a position where an equal was at. We immediately break and skip adding the number `1` to position `2` in the list. We continue with the list `[1,2]` in `ans`. We create a new list `[1,1,2]` and see that at position `0` there was another number equal to `1` (duplicate) we break and our `ans` will become `ans = [[1,2,1], [2,1,1], [1,1,2]`.

So how come we can skip adding a number `n` to any subsequent positions once we found a duplicate? That is, suppose we have a list `[1,7]` and we are currently inserting the number `n = 1` at position `0`. Sure we can skip inserting `n` at position `1` to avoid a duplicate list `[1,1,7]` but how come we can skip inserting `n` at position `2` in order to get a resulting list `[1,7,1]`? Well, this is because we also inserted `7` at every possible position in every list when we were iterating over `7` in a previous iteration. That is, we will already have `[7,1]` (because we added `7` at position `0` and `1` for the list ``). And because we already have list `[7,1]` we can construct our missing list, `[1,7,1]`, easily when we are adding (or already have added) `n = 1` at position `0` of `[7,1]`. So in other words, nothing is left behind 🙂

Full code

```class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = [[]]
for n in nums:
new_ans = []
for perm in ans:
for i in range(0, len(perm) + 1):
new_ans.append(perm[:i] + [n] + perm[i:])
if i < len(perm) and perm[i] == n:
break
ans = new_ans

return ans

def main():
solution = Solution()
print(solution.permuteUnique([1, 2, 1]))

if __name__ == "__main__":
main()
```