Permutations II

Patrick Leaton
Published: May 4, 2021, 2:48 a.m.
Problem Description

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

 

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

 

The description was taken from https://leetcode.com/problems/permutations-ii/.

Problem Solution

#O(N*N!) Time, O(N*N!) Space
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        output = []
        def backtrack(start:int) -> None:
            if start == len(nums):
                output.append(list(nums))
                return
            seen = set()
            for i in range(start, len(nums)):
                if nums[i] in seen:
                    continue
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start+1)
                nums[start], nums[i] = nums[i], nums[start]
                seen.add(nums[i])
        backtrack(0)
        return output

Problem Explanation

If a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.

This solution is basically the same as the one for the first Permutations question but the only difference is we will utilize a HashSet to avoid duplicate permutations.

Let's start by initializing our output array

        output = []

Next, we will initialize our backtrack function.

The function will take a starting index that will be the starting point for a function call's traversal through the input array.

        def backtrack(start:int) -> None:

 

The base case we will want to check at the beginning of each function call is if the starting index has reached the last index of the input array.  If that is the case then we will append the current combination of the numbers we have swapped within the input array before returning out of the function.  We will need to take a deep copy of the combo since it will be edited later and we don't want it to be overwritten.

            if start == len(nums):
                output.append(list(nums))
                return

 

Next, we will create a seen HashSet to keep track of values that we have used before in other permutations so that we don't duplicate combinations.

            seen = set()

 

We will now start creating the backtracking logic.

Let's create a loop that will scan the input array from a given starting index to the last index of the array.

This is how we will split up the scope of each permutation through recursion.  

            for i in range(start, len(nums)):

 

If the element from the current iteration is in the set, we will continue to the next iteration.

                if nums[i] in seen:
                    continue

 

Otherwise, within the current recursive call, we will swap the element in the start index with the element in the current iteration's index.

Afterward, we will recurse the function and increment the starting index by one.

                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start+1)

 

Once a Depth First Search path is complete, meaning that we have moved down a recursive path and swapped values until we have met our base case of the starting index reaching the last index of the array, or a called function has iterated all the way to the end of the input array and has broken from the loop, we will then backtrack.

We'll do this by reverting the swap we implemented previously.

                nums[start], nums[i] = nums[i], nums[start]

 

We'll want to do this so that we don't ruin the baseline that a future DFS path will begin on.  

For example, if we had [1,2,3] and we just kept swapping values and never backtracked to revert our changes, we are likely going to miss permutations and get duplicate permutations as well.

Since we just used the iteration's element in a swap, we will want to add it to the set so that we don't use it again if the same value comes up.

                seen.add(nums[i])

Once our backtrack function is created, we will just need to make the initial call by passing zero as the starting index.

Once we have all possible permutations, we will return the output array that contains each permutation.

        backtrack(0)
        return output

This illustration shows what the flow of the DFS and backtracking would look like for the input [1,2,3].

image