# Permutations II

**Problem statement**

Given a list, `nums`

, of distinct numbers, return all possible unique permutations.

**Sample input**

1 |
[1,2,1] |

**Sample output**

1 |
[[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 `[1]`

. 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 `[1]`

. 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 `[1]`

). 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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() |