Subsets

Given an array nums of unique integers, return all possible subsets of nums.

The solution set must not contain duplicate subsets. You may return the solution in any order.

Examples

• 1 ≤ nums.length ≤ 10
• -10 ≤ nums[i] ≤ 10

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion - Used to explore the decision tree where each element is either included or excluded
• Backtracking - Needed to undo choices (remove elements) after exploring one branch of the decision tree
• Bit Manipulation - Alternative approach uses bitmasks to represent subset membership

1. Backtracking

Intuition

The idea is to build all possible subsets by making a choice at each step: for every number, we have two options — include it or exclude it. This naturally forms a decision tree.

Backtracking helps us explore both choices:

• Add the current number → explore further
• Remove it (undo) → explore without it

Whenever we reach the end of the array, the current list represents one complete subset, so we store it. This systematically generates all 2ⁿ subsets.

Maintain:
res -> final list of all subsets
subset -> current subset being built

Define a recursive function dfs(i):
  If i equals the length of the input:
    Add a copy of subset to res
    Return
  
  Choice 1: include nums[i]
    Append number to subset
    Recurse to next index (dfs(i + 1))
    Remove the number (backtrack)
  
  Choice 2: skip nums[i]
    Recurse to next index (dfs(i + 1))

Start recursion with dfs(0)
Return res

Time Complexity: O(n * 2ⁿ)
Space Complexity: O(n) extra space. O(2ⁿ) for the output list.

2. Iteration

Intuition

Start with just one subset: the empty set [].

For every number in the array, we take all the subsets we have so far and create new subsets by adding the current number to each of them.

Example:

• Start: [[]]
• Add 1 → [[], [1]]
• Add 2 → [[], [1], [2], [1,2]]
• Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Each step doubles the number of subsets.

3. Bit Manipulation

Intuition

Every subset can be represented using bits. For an array of length n, there are 2ⁿ possible subsets. Each subset corresponds to a number from 0 to 2ⁿ - 1.

Example for nums = [a, b, c]:

• 000 → choose nothing → []
• 001 → choose c
• 010 → choose b
• 011 → choose b, c
• 100 → choose a

So for every integer i from 0 to (1 << n) - 1, check each bit j of i. If bit j is 1, include nums[j] in the current subset.

Common Pitfalls

Modifying the Subset After Adding to Result

When adding a subset to the result list, you must add a copy of the current subset. Otherwise, backtracking modifications will alter subsets already in the result.

# Wrong: adds reference that gets modified later res.append(subset) # Correct: add a copy res.append(subset[:])  # or list(subset)

Forgetting the Empty Subset

The power set always includes the empty subset []. Forgetting to initialize with an empty subset or starting the iteration incorrectly will miss this case.

Incorrect Index Handling in Backtracking

When recursing, start from i + 1 to avoid reusing the same element and to prevent duplicate subsets. Starting from 0 or i generates incorrect results.

# Wrong: includes current element again for j in range(i, len(nums)): # Correct: start from next element for j in range(i + 1, len(nums)):

Integer Overflow in Bitmask Approach

For the bitmask solution, 1 << n can overflow for large n. In most languages, this limits the approach to around 30 elements, though problem constraints usually keep n small.