Domain 2MediumCORE

Subsets

We are given an array of unique integers nums. The goal is to generate every possible subset from this collection, which mathematically corresponds to finding the power set.

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

78. Subsets

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


Problem Breakdown

We are given an array of unique integers nums. The goal is to generate every possible subset from this collection, which mathematically corresponds to finding the power set.

Inputs: An integer list nums with length between 1 and 10. Elements range from -10 to 10 and are guaranteed to be unique. Outputs: A list of lists containing all subsets. The order does not strictly matter, but consistency is key for testing. Implicit Constraints & Edge Cases:

  • Empty Subset: We must include the empty set [] as a valid subset (the base case).
  • Duplicates in Output: Since input elements are unique, we don’t need to handle duplicate subsets arising from identical values; however, our logic must ensure no logical duplicates occur during generation.
  • Size Limits: With N=10N=10, the output size is at most 210=10242^{10} = 1024 items. This fits easily within memory limits for typical interview constraints (usually up to a few MBs).

Intuition

If I were solving this out loud, my first thought would be permutations or sorting, but that’s incorrect because order inside the subset doesn’t matter and we want combinations, not arrangements.

The core observation here is combinatorial: for every element in nums, there are exactly two choices when building a subset—either include it or exclude it.

  • If I have 3 elements, that’s 2×2×2=82 \times 2 \times 2 = 8 combinations (2N2^N). A brute-force approach might try to generate all permutations and filter them out, which would be inefficient (Time Complexity: O(N!)O(N!) or worse) because we’d waste time generating invalid orderings.

The key insight is that this structure maps perfectly to a Decision Tree or recursion where at each step we branch into two paths. This suggests Backtracking as the optimal strategy for exploring all combinations without redundancy.

Approach

I will use a recursive backtracking approach because it cleanly models the “include/exclude” decision process and generalizes well if constraints change (e.g., allowing duplicates later).

  1. State Management: I’ll maintain current_subset to track elements currently included in the path, and an index pointer start_index to ensure we only look at remaining elements forward (preventing permutations of the same subset like [1,2] vs [2,1]).
  2. Base Case/Recording: At every recursive call, before making a decision for the next element, I record the current state of current_subset. This captures subsets formed by excluding subsequent elements as well (e.g., when we exclude index ii, that subset is valid).
  3. Iteration & Recursion: Loop from start_index to end of array:
    • Add nums[i] to path.
    • Call recursion with i + 1.
    • Remove last element (backtrack) so we can try the next combination starting at same level.

Complexity Analysis

  • Time Complexity: O(N⋅2N)O(N \cdot 2^N), where NN is the length of nums. There are 2N2^N subsets in total. For each subset added to our result list, we perform work proportional to its size (copying or appending). The sum of sizes across all nodes in a binary tree structure sums up linearly with respect to depth times number of leaves.
  • Space Complexity: O(N)O(N) for the recursion stack and temporary current_subset storage during traversal. Note: This does not include the space required for the output list, which is inherently O(2N⋅N)O(2^N \cdot N).

Solution

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        # Helper function to perform backtracking
        def backtrack(start_index, current_subset):
            # Add a copy of the current subset to results. 
            # We do this at every step because excluding remaining elements 
            # also forms valid subsets (e.g., if we stop here).
            res.append(current_subset[:]) 
            
            for i in range(start_index, len(nums)):
                # Include nums[i] and move forward
                current_subset.append(nums[i])
                
                backtrack(i + 1, current_subset)
                
                # Backtrack: remove the last element to explore other combinations
                current_subset.pop()

        # Start recursion with empty subset at index 0
        backtrack(0, [])
        
        return res

Edge Cases Handled

  • Single Element Array: The loop runs once, adds [[]], then [[num]]. Correct.
  • Negative Numbers: Since we treat elements as values to be appended, the sign doesn’t affect logic or comparison operations used in iteration.
  • Empty Input (Hypothetical): If nums were empty, loop range is 0-0, recursion adds [[]], returns correct result immediately. Though constraints say length ≥\ge 1.
  • Max Constraints: With N=10N=10, the solution generates ~1KB of data roughly (depending on integer size), well within standard memory limits for Python lists.