Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Additional information

• 0 <= nums.length <= 10
• -10 <= nums[i] <= 10

Example 1:

Input: nums = [1, 2, 2]

Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Example 2:

Input: nums = [0]

Output: [[], [0]]

Iterative Generation with Sets (Brute Force)

Intuition

Since the input array can contain duplicates, generating subsets using the standard iterative approach will inevitably create duplicate subsets. For instance, if the array is [2, 2], the standard algorithm will generate [2] twice (once for the first 2, and once for the second 2).

To forcefully resolve this, we can generate absolutely every subset just like normal. But before adding a subset to our final answer pool, we sort it and convert it into a tuple. We then store these tuples in a set. The set will automatically filter out any identical duplicate subsets.

Algorithm

1. Initialize a set called res_set and add an empty tuple to it: set([()]).
2. Iterate through every num in the nums array.
3. Inside the loop, iterate through a current snapshot of all subsets in res_set.
4. For each existing subset, create a new subset by adding num to it.
5. Sort this new subset, convert it to a tuple, and add it to res_set.
6. Once all subsets are generated and filtered, convert the set of tuples back to a list of lists and return.

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    res_set = set([()])
    
    for num in nums:
        # Create a snapshot of the current set to iterate over
        current_subsets = list(res_set)
        
        for subset in current_subsets:
            # Create a new subset, sort it, and tuple it
            new_subset = list(subset) + [num]
            new_subset.sort()
            res_set.add(tuple(new_subset))
            
    # Convert back to list of lists
    return [list(subset) for subset in res_set]

Time & Space Complexity

• Time complexity: O(N * 2^N log N)

• Reason: We generate up to 2^N subsets. For each subset, we append an element and sort the resulting array (which can be up to length N). Sorting takes O(N log N) time, making the overall time complexity bounded by O(N * 2^N log N) in the worst case.

• Space complexity: O(N * 2^N)

• Reason: The res_set holds up to 2^N unique subsets, and each subset takes up to O(N) space.

Recursive Backtracking with Pruning - Optimal

Intuition

We can build the subsets without generating a single duplicate by using Depth-First Search (DFS) backtracking. To make this work, we must sort the input array first. By sorting the array, all duplicate numbers end up right next to each other (e.g., [1, 2, 2, 2, 3]).

In our decision tree, at every step we have two choices:

1. Include the current number and recurse.
2. Exclude the current number and recurse.

Here is the magic trick: if we choose to exclude the current number, we cannot include any identical numbers that immediately follow it! If we skip the first 2 but decide to include the second 2, we are just creating the exact same branch we just finished exploring. By skipping all adjacent duplicates during the "exclude" step, we perfectly prune the tree.

Algorithm

1. Sort the nums array. This is strictly required for the duplicate pruning logic to work.
2. Initialize an empty list res for the final subsets.
3. Create a recursive helper dfs(i, current_subset) where i is our current index in nums.
4. Base Case: If i == len(nums), we reached the end of the array. Append a .copy() of current_subset to res and return.
5. Decision 1: Include the current number.

• Append nums[i] to current_subset.
• Recursively call dfs(i + 1, current_subset).

6. Decision 2: Exclude the current number (and all duplicates).

• Backtrack by popping the last element: current_subset.pop().
• Use a while loop to advance the index i as long as i + 1 is within bounds and nums[i] == nums[i + 1].
• Recursively call dfs(i + 1, current_subset).

7. Call dfs(0, []) to start the recursion.
8. Return res.

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    # Sorting is mandatory to group duplicates together
    nums.sort()
    res = []
    
    def dfs(i, current_subset):
        if i == len(nums):
            res.append(current_subset.copy())
            return
            
        # Decision 1: Include nums[i]
        current_subset.append(nums[i])
        dfs(i + 1, current_subset)
        
        # Decision 2: Exclude nums[i]
        current_subset.pop()
        
        # PRUNING: Skip all subsequent identical numbers
        while i + 1 < len(nums) and nums[i] == nums[i + 1]:
            i += 1
            
        dfs(i + 1, current_subset)
        
    dfs(0, [])
    return res

Time & Space Complexity

• Time complexity: O(N * 2^N)

• Reason: Sorting the array takes O(N log N) time. The backtracking tree generates only unique subsets, which in the worst case (all unique elements) is 2^N nodes. At each leaf node, making a copy of the subset takes O(N) time. The dominating factor is O(N * 2^N).

• Space complexity: O(N)

• Reason: Excluding the output array, the auxiliary space used is entirely dictated by the maximum depth of the recursion stack and the current_subset array, both of which are bounded by O(N).