Permutations II medium

Problem Statement

Given a collection of numbers, nums, that might contain duplicates, return all unique permutations of the numbers. 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]]

Steps

1. Sort the input array: Sorting the input array allows us to easily identify and skip duplicate permutations.

2. Backtracking: Use a backtracking algorithm to generate all possible permutations. The core idea is to recursively explore all possible positions for each number.

3. Skip Duplicates: When choosing a number for a position, skip numbers that are the same as the previously chosen number at that level of recursion. This prevents generating duplicate permutations.

4. Base Case: The base case for recursion is when we have placed all numbers in the permutation. Add this permutation to the result.

5. Recursive Step: For each available number, place it in the current position, recursively generate the rest of the permutation, and then backtrack (remove the number from the current position).

Explanation

The backtracking approach systematically explores all possible arrangements of the numbers. Sorting the input array significantly improves efficiency by allowing us to quickly identify and avoid duplicates. The condition i > 0 and nums[i] == nums[i - 1] and i - 1 not in used ensures we only consider unique permutations.

Code

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()  # Sort to easily handle duplicates
        n = len(nums)
        used = set()  # Keep track of used indices in the current permutation

        def backtrack(current_permutation):
            if len(current_permutation) == n:
                result.append(current_permutation[:])  # Add a copy to avoid modification
                return

            for i in range(n):
                if i not in used:
                    # Skip duplicates at the same recursion level
                    if i > 0 and nums[i] == nums[i - 1] and i - 1 not in used:
                        continue

                    used.add(i)
                    current_permutation.append(nums[i])
                    backtrack(current_permutation)
                    current_permutation.pop()  # Backtrack: remove the last element
                    used.remove(i)

        backtrack([])
        return result

Complexity

• Time Complexity: O(N! * N), where N is the length of the input array. Generating all permutations takes O(N!) time, and adding each permutation to the result list takes O(N) time.

• Space Complexity: O(N) due to the recursive call stack and the used set. The result list can also take O(N!) space in the worst case (no duplicates), but this is not part of the recursive function's space usage.