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

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()