Given an integer array nums of unique elements, return all possible subsets (the power set). The solution must not contain duplicate subsets.

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

Constraints

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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Every element has two choices: include or exclude. With n elements, there are 2^n subsets total.

Backtracking Approach

Use DFS with a start index to avoid duplicates. At each level, we first record the current path as a valid subset, then try adding each remaining element and recurse.

Walk-Through: nums = [1, 2, 3]

dfs(start=0, path=[])        → record []
├─ add 1 → dfs(start=1, path=[1])    → record [1]
│  ├─ add 2 → dfs(start=2, path=[1,2])  → record [1,2]
│  │  └─ add 3 → dfs(start=3, path=[1,2,3]) → record [1,2,3]
│  └─ add 3 → dfs(start=3, path=[1,3])  → record [1,3]
├─ add 2 → dfs(start=2, path=[2])    → record [2]
│  └─ add 3 → dfs(start=3, path=[2,3])  → record [2,3]
└─ add 3 → dfs(start=3, path=[3])    → record [3]

The start parameter ensures we only pick elements after the current index, preventing duplicate subsets like [2,1] when [1,2] already exists.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Approach 1: Backtracking – O(n · 2^n)

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

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: Every element has two choices: include or exclude. With n elements, there are 2^n subsets total.

Walkthrough — input nums = [1,2,3], expected output [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Bitmask Enumeration – O(n · 2^n)

Each integer from 0 to 2^n - 1 represents a subset: bit j is set means include nums[j].

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

Time: O(n · 2^n) Space: O(n) per subset (excluding output)

Common Mistakes

  • Forgetting path.pop_back() after the recursive call (breaks backtracking)
  • Using i instead of i + 1 in the recursive call (generates permutations, not subsets)
  • Not recording the path at the start of each call (misses the empty subset and partial subsets)

Key Takeaways

  • Backtracking template: push → recurse → pop. The start index prevents revisiting earlier elements
  • Bitmask alternative: natural for small n (≤ 20), iterative and easy to reason about
  • This is the foundation for LC 90 (Subsets II with duplicates) – just add a sort + skip condition

References

Template Reference