Subsets — Solution

Problem

Given an array of unique integers, return every possible subset of those integers, including the empty set. Each element either appears in a subset or it doesn't — there's no repetition of elements within a subset, and [1,2] and [2,1] count as the same subset.

• Input: nums = [1, 2, 3]
• Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
• Explanation: All 8 (2³) subsets of a 3-element array, including the empty subset.

Intuition

Every element faces exactly one binary choice: be included or be excluded. That gives exactly 2^n subsets for n elements. We can build them iteratively — each new element doubles the collection by appending it to every existing subset — or recursively with a backtracking DFS that records the current partial subset at every node in the decision tree.

Approach 1 — Iterative Cascading

Start with just the empty subset. For each element, generate new subsets by adding that element to every subset already collected, then extend the collection with those new subsets.

1. Initialize subsets with one entry: the empty list.
2. For each num in nums:
   • Snapshot the current size of subsets before extending.
   • For every existing subset (up to the snapshot), create a copy with num appended.
   • Add those new subsets to subsets.
3. Return subsets.

1def subsets(nums):
2    result = [[]]
3    for num in nums:
4        # each existing subset spawns a copy that includes num
5        result += [subset + [num] for subset in result]
6    return result

Time: O(n × 2^n) — each of n elements is added to all 2^(i−1) subsets collected so far.

Space: O(n × 2^n) — the output itself; no additional stack or auxiliary structure.

Approach 2 — Backtracking

Use DFS: at each call, record the current path as a valid subset (every partial state is valid for this problem), then try extending it with each remaining element one at a time, backtracking after each choice.

1. Start DFS with an empty path and start_index = 0.
2. At the top of each call, append a copy of path to result.
3. Loop i from start_index to the end of nums:
   • Add nums[i] to path.
   • Recurse with start_index = i + 1 so elements aren't reused.
   • Pop nums[i] from path to undo the choice.
4. Return result.

1def subsets(nums):
2    result = []
3
4    def backtrack(start_index, path):
5        result.append(path[:])  # copy — not a reference to the mutable list
6        for i in range(start_index, len(nums)):
7            path.append(nums[i])
8            backtrack(i + 1, path)
9            path.pop()  # undo before trying the next element
10
11    backtrack(0, [])
12    return result

Time: O(n × 2^n) — 2^n subsets, each of average length n/2.

Space: O(n) for the recursion stack and the path buffer, plus O(n × 2^n) for the output.

Complexity Summary

Common Mistakes

• Storing a reference instead of a copy — result.append(path) in Python records the same list object, so every "stored" subset silently changes as path mutates. Always use path[:] in Python or new ArrayList<>(path) in Java.
• Iterating over result while modifying it — in the iterative approach, snapshot currentSize = len(result) before the inner loop; without it you'll process newly added subsets as inputs and generate duplicates.
• Forgetting the empty subset — the empty set is always a valid subset. In iterative, start with [[]]. In backtracking, adding path[:] before the loop (not after) ensures the empty path is captured at the root.
• Passing i instead of i + 1 to the recursive call — backtrack(i, path) allows the same index to be revisited, producing repeated elements in subsets rather than distinct subsets.
• Assuming the output must be sorted — the problem does not require a specific order. If a test harness does a direct equality check, sort both the subsets themselves and the outer list before comparing.

Related Problems

• subsets-ii — same problem but the input contains duplicates, requiring a sort + skip-duplicate step inside the backtracking loop
• permutations — also enumerates all combinations via backtracking, but order matters so elements can be revisited from a "used" set instead of a start index
• combination-sum-ii — backtracking over candidates with a target sum and duplicate-skipping, built on the same DFS skeleton
• palindrome-partitioning — enumerate all ways to partition a string, using the same "add current result, then try each extension" backtracking pattern
• letter-combinations-of-a-phone-number — enumerate all combinations from a digit mapping; the same backtracking template applied to a fixed branching factor