Domain 2MediumCORE

Subsets II

We need to generate the power set (all possible subsets) of a given integer array nums. The critical constraint here is that if the input contains duplicate numbers, our output must not contain any duplicate subsets. For example, [1, 2, 2] should produce exactly one subset containing just [2], even though there are two instances of 2 in the input.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Backtracking

90. Subsets II

Model: qwen3.5:9b
Topics: Array,Backtracking
FAANG asked: 1
Acceptance rate: 49.1%


Problem Breakdown

We need to generate the power set (all possible subsets) of a given integer array nums. The critical constraint here is that if the input contains duplicate numbers, our output must not contain any duplicate subsets. For example, [1, 2, 2] should produce exactly one subset containing just [2], even though there are two instances of 2 in the input.

Inputs: An integer array nums. Outputs: A list of lists representing unique subsets. Constraints & Edge Cases:

  • Array length is between 1 and 10 (small scale, but logic must be general).
  • Values can be negative or positive; this does not affect subset generation logic, only comparison values.
  • Duplicates are the primary source of complexity here. We cannot simply use a Set to deduplicate at the end because that would require storing all subsets in memory first (O(2N)O(2^N) space), which is less efficient than pruning during backtracking.

Intuition

The standard approach for generating power sets uses recursion (backtracking). If we ignore duplicates, every element has two choices: either include it or exclude it from the current subset being built. This forms a binary decision tree of depth NN.

If nums contains duplicates and we don’t handle them specifically during traversal, our backtracking will generate identical subsets multiple times (e.g., picking the first ‘2’ vs the second ‘2’). To fix this efficiently without storing all results in memory to filter later:

  1. Sort the array first. This groups duplicate values together adjacent to each other.
  2. During backtracking, when iterating through available elements at a specific recursion level (defined by start_index), if we encounter an element that is identical to the previous one (nums[i] == nums[i-1]) and it’s not the first choice in this loop iteration, we skip it.
  3. This pruning ensures that for any given depth of our decision tree, we only pick a specific value once per unique combination path at that level.

Approach

We will use Backtracking (Depth-First Search).

  1. Sort nums to group duplicates.
  2. Define a recursive function backtrack(start_index, current_path).
  3. At each call, add the copy of current_path to our results list. This captures every valid subset formed so far.
  4. Iterate through elements starting from start_index.
  5. Crucial Step: Check if i > start_index and nums[i] == nums[i-1]. If true, skip this element. Why? Because we are currently at a specific level of the recursion tree (a subset length). We want to ensure that for this specific depth, we don’t branch on duplicate values multiple times unless they represent distinct starting points from previous levels. Since duplicates are sorted adjacent, picking nums[i-1] covers all subsets startable by that value; skipping nums[i] prevents generating the same subset via a different index at the same level.
  6. Add element to path, recurse with i + 1, then backtrack (remove element).

Complexity Analysis

Time Complexity: O(N⋅2N)O(N \cdot 2^N). In the worst case (no duplicates), there are 2N2^N subsets. Each subset takes up to O(N)O(N) time to copy into our result list during recursion steps, and we iterate through elements at each step. With pruning for duplicates, it is strictly less than or equal to this bound in practice, but asymptotically bounded by the same worst case (e.g., all unique inputs).

Space Complexity: O(N)O(N). This refers to auxiliary space excluding the output storage. We need O(N)O(N) stack depth for recursion and a path list of size up to NN during traversal. The result set itself takes O(2N⋅N)O(2^N \cdot N) memory, which is standard for this problem type.

Solution

class Solution:
    def subsetsWithDup(self, nums):
        # Sort the array so duplicates are adjacent; essential for pruning logic
        nums.sort()
        
        result = []
        
        def backtrack(start_index, current_path):
            # Add a copy of the current path to results at every step
            # This captures all valid subsets including empty set (initial call)
            result.append(current_path[:]) 
            
            for i in range(start_index, len(nums)):
                # Pruning logic: 
                # If we are not at the first element of this recursion level (i > start_index),
                # and the current number is a duplicate of the previous one, skip it.
                # This prevents generating identical subsets from different indices in the same loop iteration.
                if i > start_index and nums[i] == nums[i - 1]:
                    continue
                
                # Include element
                current_path.append(nums[i])
                
                # Recurse with next index to avoid reusing elements at this level
                backtrack(i + 1, current_path)
                
                # Backtrack: remove last added element before trying the next branch
                current_path.pop()

        backtrack(0, [])
        
        return result

Edge Cases Handled

  • All duplicates (e.g., [2, 2]): The sorting places them adjacent. The pruning condition nums[i] == nums[i - 1] ensures only one branch is taken for the value ‘2’ at each recursion depth level, resulting in correct unique subsets: [], [2], [2, 2].
  • No duplicates (e.g., [0, 1, 3]): The condition nums[i] == nums[i - 1] is never met; the code behaves exactly like standard Subsets problem.
  • Negative numbers: Since we rely on value equality (==) rather than magnitude or sign for logic flow, negative integers are handled correctly as long as they maintain relative order after sorting (e.g., [-2, -1, 0]).