Subsets

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

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

Examples

Example 1

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

Example 2

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

Intuition

A subset is any combination of elements (including empty set and full set).

For array [1,2,3], at each position we have 2 choices:

• Include the element
• Exclude the element

This creates a binary decision tree with 2^n leaf nodes (all subsets).

Key insight: Use backtracking to explore all paths in decision tree.

Pattern Recognition

This is a Backtracking Decision Tree problem:

• Binary choices (include/exclude)
• Explore all possibilities
• Collect results at each step

Approach

Backtracking Solution

Template:

def backtrack(start, current):
  result.append(current.copy())  # Add current subset

  for i in range(start, len(nums)):
    current.append(nums[i])      # Choose
    backtrack(i + 1, current)    # Explore
    current.pop()                 # Unchoose (backtrack)

Why this works:

• Start with empty subset
• For each element, create subsets with and without it
• Backtracking ensures we explore all combinations

Alternative: Cascading

Start with [[]], for each num, add num to all existing subsets:

[] → add 1 → [[],[1]]
[[],[1]] → add 2 → [[],[1],[2],[1,2]]

Bit Manipulation

Each subset corresponds to a binary number:

• 000 = []
• 001 = [3]
• 010 = [2]
• 011 = [2,3]
• etc.

Edge Cases

• Empty array → [[]]
• Single element → [[], [element]]
• Large array (up to 2^n subsets)

Complexity Analysis

• Time: O(n × 2^n)

  • 2^n subsets
  • Each subset takes O(n) to copy

• Space: O(n) recursion depth

  • Not counting output (which is 2^n)