Problem Statement in English

You’re given an integer array nums that may contain duplicates. Your task is to return all possible subsets (the power set) of the array, ensuring that no duplicate subsets are included in the result.

Approach

In order to avoid duplicates, we need to be able to going ahead when we just skipped a number and encounter the same number again.

This is where sorting the array comes in handy. By sorting the array, we can easily skip over duplicates during our backtracking process.

The rest of the approach is similar to the 78. Subsets, where we model the solution as a decision tree. We will explore two options at each index: include the current number in the subset or exclude it.

And we’re done!

Solution in Python


class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        res = []
        curr = []
        N = len(nums)
        
        nums.sort()
        
        def dfs(i):
            if i >= N:
                res.append(curr.copy())
                return

            curr.append(nums[i])
            dfs(i + 1)
            curr.pop()

            i += 1
            while i < N and nums[i] == nums[i - 1]:
                i += 1
            dfs(i)

        dfs(0)
        return res

Complexity

  • Time: $O(2^n)$
    Since we generate $2^n$ possibilities per choice, and since we have $n$ choices, that’s $n*2^n$.

  • Space: $O(n)$
    Since we are using a recursive function, the maximum depth of the recursion tree will be n, which is the length of the input array. Therefore, the space complexity is $O(n)$ due to the recursion stack.

And we are done.