GitHub

Subsets (Power Set) medium

Description

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and you may return them in any order.

Examples

> Case 1:
    Input:  nums = [1, 2, 3]
    Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
    # 8 subsets in total — 2^3.
 
> Case 2:
    Input:  nums = [0]
    Output: [[], [0]]

Constraints

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All elements of nums are unique.

Intuition — the include/exclude decision

For every element, we have two choices: include it in the current subset, or skip it. Make those choices for every element, and the leaves of the resulting decision tree are exactly the 2^n subsets.

nums = [1, 2, 3]

                           []
              /                          \
          include 1                   skip 1
            [1]                          []
        /         \                 /          \
   include 2    skip 2          include 2    skip 2
     [1,2]       [1]              [2]          []
    /     \     /  \             /  \         /  \
  +3     -3   +3   -3          +3   -3      +3   -3
[1,2,3] [1,2] [1,3] [1]       [2,3] [2]    [3]   []

Eight leaves → eight subsets. That’s it.

Approach 1: Backtracking — include then exclude

The cleanest recursive style: at index i, include nums[i] and recurse, then exclude it and recurse.

⚠️

Notice current[:] (Python) and new ArrayList<>(current) (Java) when recording a result — we have to copy the current subset, because the same list keeps getting mutated as the recursion continues. Forgetting this is the #1 bug in backtracking problems.

Approach 2: “Pick from the rest” style

A slightly different shape — at each step we iterate over the remaining elements and recurse on each. The current current is always a valid subset and gets recorded before the loop.

Both approaches are correct. Use whichever feels more natural — the start index version generalizes more cleanly to combination problems where order matters.

Approach 3: Bitmask (iterative)

There are 2^n subsets, and the bits of an integer from 0 to 2^n - 1 correspond one-to-one with them. Bit j of mask set → include nums[j] in the subset.

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[j] for j in range(n) if mask & (1 << j)]
        result.append(subset)
    return result

No recursion at all — just iterate from 0 to 2^n - 1. Clean for fixed small n (the constraints cap us at n <= 10).

Analysis

Time: O(n · 2^n) — 2^n subsets, each up to n elements to copy.
Space: O(n) for the call stack and the working subset (the output is necessarily O(n · 2^n)).

The subset/permutation/combination family

This problem is the gateway to a whole family. The shape of the recursion is what changes:

Problem	Choices per call	Output size
Subsets	include or skip	`2^n` subsets
Combinations(k)	pick any of remaining, fixed length k	`C(n, k)`
Permutations	pick any unused element	`n!` permutations

Master the subsets backtracking shape and the other two come almost for free.

Generate Parentheses Permutations