Subsets — Step-by-Step Visualization

Algorithm Pattern

Recursive Backtracking (Decision Tree)

Key Idea

At each index, we make a binary decision: either INCLUDE the current element in the subset or SKIP it and move on. This builds a decision tree whose leaves are all 2^n subsets. Unlike Combination Sum, we always add the current path to results — there's no target to hit.

Step-by-Step Approach

1. Define a recursive `dfs(index, currentSubset)` function.
2. At every call, immediately add a COPY of `currentSubset` to results.
3. Decision 1 (Include): Push `nums[index]` to `currentSubset`, recurse into `index + 1`.
4. Backtrack: Pop the element after the recursive call finishes.
5. Decision 2 (Skip): Recurse into `index + 1` WITHOUT pushing any element.
6. Stop when `index` reaches the end of `nums`.

Common Gotchas

• Add a copy of the subset at EVERY call — not just at leaf nodes. This is different from problems with a target sum.
• The empty subset `[]` is always the first result added.