Subsets

Difficulty: Medium Source: NeetCode

Problem

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.

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]]

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion — calling a function with a smaller subproblem
• Backtracking — making a choice, recursing, then undoing the choice

1. Cascading (Iterative)

Intuition

Start with one subset: the empty set. For each element in nums, take every existing subset, append the current element to it, and add the result as a new subset. After processing all elements, you have the full power set. No recursion required — it’s a clean iterative build-up.

Algorithm

1. Initialize result = [[]].
2. For each num in nums:
   • For each existing subset s in result, create s + [num].
   • Extend result with all the new subsets.
3. Return result.

Solution

def subsets_cascading(nums):
    result = [[]]
    for num in nums:
        new_subsets = [s + [num] for s in result]
        result.extend(new_subsets)
    return result


print(subsets_cascading([1, 2, 3]))
# [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
print(subsets_cascading([0]))
# [[], [0]]

Complexity

• Time: O(n * 2^n) — we process each of the 2^n subsets, each taking up to O(n) to copy
• Space: O(n * 2^n) — storing all subsets

2. Backtracking

Intuition

At each index i, we make a binary choice: include nums[i] in the current subset or skip it and move to i+1. By exploring both branches for every element, we naturally enumerate all 2^n subsets. We record a snapshot of the current subset at every node of the recursion tree (not just at the leaves), so every partial selection is captured.

Algorithm

1. Define backtrack(start, current).
2. Append a copy of current to result (every state is a valid subset).
3. For each index i from start to len(nums) - 1:
   • Append nums[i] to current.
   • Recurse with start = i + 1.
   • Pop nums[i] from current (backtrack).
4. Call backtrack(0, []) to kick things off.

Solution

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(list(current))  # snapshot of current subset
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()  # undo the choice

    backtrack(0, [])
    return result


print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
print(subsets([0]))
# [[], [0]]

Complexity

• Time: O(n * 2^n) — 2^n subsets, each costs O(n) to copy
• Space: O(n) — recursion depth is at most n (excluding output)

Common Pitfalls

Appending current instead of list(current). If you do result.append(current), you’re storing a reference to the same list that gets modified throughout the recursion. Always append a copy: result.append(list(current)) or result.append(current[:]).

Incrementing start incorrectly. When you recurse, pass i + 1 (not start + 1). Using start + 1 would only ever look one position ahead, missing many subsets.

Not popping after the recursive call. Every append inside the loop must have a corresponding pop after the recursive call. Forgetting the pop means your current list keeps growing across branches.