Hoarding programming problems for you!

### 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

Sample output

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