Given an integer array nums of distinct elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. You may return the subsets in any order.
mask & (1 << j)) controls nums[j]. Any fixed assignment works as long as it's consistent.sub = (sub - 1) & mask is a classic extension used in subset-sum dynamic programming.Input: nums = [1, 2, 3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] All 2^3 = 8 subsets, one per 3-bit pattern from 000 to 111. Any order is accepted.
Input: nums = [0] Output: [[],[0]] The two subsets of a single element: without it and with it.
- 1 <= nums.length <= 10 - -10 <= nums[i] <= 10 - All the numbers of nums are unique.
There are exactly 2^n subsets of an n-element set — and that 2^n is a giant hint. Every subset corresponds to a yes/no choice per element: is this element in or out? That's n bits, which is just a number from 0 to 2^n - 1. So generating all subsets is nothing more than counting in binary.
n bits, each an independent on/off switch.mask & (1 << j) checks whether bit j of mask is set.n-element set has exactly 2^n subsets.“Does the order of subsets matter?”
No — any order is fine, and each subset's internal order is free too.
“Is the empty subset included?”
Yes — the power set contains the empty set and the full set.
“Are the elements distinct?”
Yes, so no subset can be duplicated and no dedup is needed.
“How large is n?”
Small — up to about 10 — because the output itself has 2^n subsets.
An n-element set has 2^n subsets, one per in/out choice across the elements.
That's n bits, i.e. a number from 0 to 2^n - 1.
So I'll loop those numbers and, for each, pick the elements whose bit is set.
Worked example — nums = [1, 2, 3], so 2^3 = 8 subsets
mask bits(cba) subset 0 000 [] 1 001 [1] 2 010 [2] 3 011 [1, 2] 4 100 [3] 5 101 [1, 3] 6 110 [2, 3] 7 111 [1, 2, 3]
Each element is an independent in/out switch, so a subset is an n-bit pattern. There are 2^n patterns and 2^n subsets — a perfect one-to-one match.
Loop mask over that range; for each, include nums[j] exactly when bit j is set (mask & (1 << j)). No recursion, no duplicates, no missed cases.
The classic include/exclude backtracking makes the same binary choice per element — it just spends it down a call stack instead of across a counter. Both are O(2^n * n).
| Bitmask counting | Backtracking | |
|---|---|---|
| Idea | Loop 0..2^n-1; bits pick the elements | Recurse, choosing include/exclude per element |
| Time | O(2^n * n) | O(2^n * n) |
| Extra space | O(1) beyond the output | O(n) recursion stack |
Both do the same 2^n work; the bitmask version is iterative with no call stack, which is why it's the natural fit here. Full code is in the Approaches selector below.
Key takeaway
Subsets are n-bit numbers in disguise. Count from 0 to 2^n - 1, and for each number let its set bits pick the elements. The whole power set falls out of a single loop — the cleanest possible use of "a bit per choice."
for mask in 0 .. 2^n - 1:
subset = [ nums[j] for j in 0..n-1 if mask has bit j set ]
add subset to result
return result