Subsets

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set).

Examples

The brute-force approach

For each element, decide independently whether to include it or not. Generate every possible binary string of length n (where 0 = exclude, 1 = include), build the corresponding subset for each string, and collect them all.

result = []

for mask from 0 to 2^n - 1:
    subset = []
    for i from 0 to n - 1:
        if bit i of mask is set:
            subset.append(nums[i])
    result.append(subset)

return result

This works and is actually O(n × 2^n), not worse than backtracking. The downside is it doesn't generalize. The moment you add a constraint (subsets that sum to a target, subsets of length exactly k), the bitmask approach has no natural place to prune. You generate everything and filter at the end.

Spotting the pattern

This is a Backtracking problem. The key question to ask yourself:

At every level of the recursion, a valid subset already exists in `current`. When should you record it, only at the leaves, or at every call?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.