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