View on NeetCode
View on LeetCode

Problem

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.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

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

Solution

Approach: Backtracking with Duplicate Skipping

The key insight is to sort the array first, then skip duplicate elements at the same recursion level to avoid duplicate subsets.

Implementation

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()  # Sort to group duplicates together

        def backtrack(start, path):
            result.append(path[:])

            for i in range(start, len(nums)):
                # Skip duplicates at same level
                if i > start and nums[i] == nums[i-1]:
                    continue

                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()

        backtrack(0, [])
        return result

Complexity Analysis

• Time Complexity: O(n * 2^n), where n is the length of nums. Sorting is O(n log n), backtracking generates 2^n subsets.
• Space Complexity: O(n) for recursion depth (not counting output).

Key Insights

1. Sort First: Sorting groups duplicate elements together, making them easy to skip.

2. Skip at Same Level: The condition i > start ensures we skip duplicates only at the same recursion level, not in different branches.

3. First Occurrence Allowed: We always include the first occurrence of a duplicate, but skip subsequent ones at the same level.

4. Different from Subsets I: The main difference is the duplicate-skipping logic. Without it, we’d get duplicate subsets.

5. Example Trace: For [1,2,2], we include [] then [1], then [1,2], [1,2,2]. When backtracking to root, we include [2] but skip the second 2 at the same level.