Permutations Ii - Leetcode Solution

Problem Statement:

Given an array nums of n integers, return an array of all the unique permutations of nums. You can return the answer 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]]

Solution:

Approach:

This problem can be solved by using DFS (Depth First Search) technique. We can use a recursive function to generate permutations. The key to generating unique permutations is to skip over identical values. In order to skip over a duplicate value, we first need to sort the array. Once the array is sorted, we can use a boolean array to keep track of which values we have visited. Whenever we encounter a duplicate value, we only consider its corresponding value if the previous duplicate value has been used in the current permutation. This guarantees that we will only generate unique permutations.

Algorithm:

1. Sort the given array in ascending order, to avoid duplicate permutations.
2. Create an empty list to store permutations.
3. Define a recursive function to generate permutations. 3.1. Base condition: If the length of the current permutation is equal to the length of the given array, append the permutation to the list. 3.2. Initialize a boolean array of length n to keep track of which values we have already used in the current permutation. 3.3. Loop through the array and for each value: 3.3.1. If the value has already been used in the current permutation or (if the current value is equal to the previous value and the previous value has not been used), continue. 3.3.2. Set the current value in the boolean array to True. 3.3.3. Append the current value to the current permutation. 3.3.4. Recursively call the function with the updated permutation. 3.3.5. Remove the current value from the current permutation. 3.3.6. Reset the boolean flag for the current value to False.
4. Call the recursive function with an empty list and the boolean array initialized to False.
5. Return the list of permutations.

Time Complexity:

The time complexity of the above algorithm is O(n*n!), where n is the length of the input array. This is because there are n! permutations and we need to check each permutation to see if it is unique.

Space Complexity:

The space complexity of the above algorithm is O(n!), where n is the length of the input array. The space is used to store the output list of permutations.

Code:

Here is the Python implementation of the above approach:

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]:

    def permuteHelper(nums, curr_perm, used, result):
        if len(curr_perm) == len(nums):
            result.append(curr_perm.copy())
            return
        
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
                continue
            
            used[i] = True
            curr_perm.append(nums[i])
            
            permuteHelper(nums, curr_perm, used, result)
            
            used[i] = False
            curr_perm.pop()
    
    nums.sort()
    result = []
    permuteHelper(nums, [], [False]*len(nums), result)
    
    return result

Explanation:

1. We initialize a solution object of the Solution class, which is required to submit the solution on LeetCode.
2. The permuteUnique function takes an array of integers as input and returns a list of unique permutations.
3. The permuteHelper function takes an array of integers, current permutation, boolean array to keep track of used values, and a list to store final permutations.
4. If the length of the current permutation is equal to the length of the input array, we append the permutation to the result list and return.
5. We loop through the input array and for each value, we check if it has already been used in the current permutation or if it is a duplicate and the previous duplicate value has not been used. If any of these conditions is true, we continue to the next iteration.
6. Otherwise, we set the current value as used in the boolean array and append it to the current permutation.
7. We recursively call the permuteHelper function with the updated permutation and boolean array.
8. After returning from the function call, we reset the boolean flag for the current value to False and remove the current value from the current permutation.
9. We call permuteHelper function with an empty list, boolean array initialized to False, and the sorted input array.
10. We return the final list of unique permutations.

1