Subsets
Problem statement
You're given an array of unique integers, nums. Return every possible
subset of nums — its full power set — including the empty subset and
nums itself. Order doesn't matter, and no subset should appear twice.
Think of it as generating every possible combination of feature flags you might want to test together, from none of them enabled to all of them at once.
Examples
Example 1
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Explanation: Every one of the 2³ = 8 possible combinations of including or excluding each of 1, 2 and 3 is represented exactly once, from the empty subset to the full array.
Example 2
Input: nums = [0]
Output: [[],[0]]
Explanation: A single-element array has exactly 2¹ = 2 subsets: the empty one, and the one containing that element.
Hints
Approach
Optimal: Bitmask
Intuition
Every subset corresponds to exactly one n-bit binary number: bit i is 1
if nums[i] is included, 0 if it isn't. Counting from 0 to 2ⁿ − 1 in
binary therefore visits every possible combination exactly once, with no
explicit branching or recursion required — just a loop over every integer
in that range, reading off its bits.
Steps
- Compute
n = len(nums)andtotal = 2ⁿ. - For each
maskfrom0tototal - 1:- Build a subset by checking, for each bit position
ifrom0ton - 1, whether bitiofmaskis set; if so, includenums[i]. - Add the finished subset to the result.
- Build a subset by checking, for each bit position
- Return the result.
Dry run
nums = [1, 2, 3], n = 3, total = 8 — bit 0 controls 1, bit 1
controls 2, bit 2 controls 3:
| mask | binary (bit2 bit1 bit0) | 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] |
This produces the 8 subsets in exactly the same order as Example 1's expected output.
Edge cases: nums with one element gives total = 2 masks (0 and 1),
producing [] and [that element] — matching Example 2. The constraint
caps n at 10, so 2ⁿ never exceeds 1024, keeping this comfortably fast
despite being exponential in general.
Complexity
Time O(n · 2ⁿ) - the same total work as the other two approaches, since there's no way around visiting all 2ⁿ subsets and writing up to n elements into each. What changes is the overhead: a flat loop over integers with simple bit tests, no recursion and no repeated copying of growing lists, which tends to make this the fastest of the three in practice even at an identical worst-case complexity.
Space O(n) - extra beyond the output, for the single subset being built per mask — no recursion stack needed at all.
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
result = []
for mask in range(1 << n):
subset = [nums[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
if __name__ == "__main__":
print(Solution().subsets([1, 2, 3])) # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
print(Solution().subsets([0])) # [[], [0]]RecapThe whole problem in a few lines, for the night before
- Spot it: "generate every possible subset or combination of a small set" — power-set, 2ⁿ growth
- Idea: build subsets up one element at a time (cascading), or make an explicit include/exclude choice per element (backtracking), or treat each subset as a binary number (bitmask) — all three touch every one of the 2ⁿ subsets, just with different overhead
- Cost: O(n · 2ⁿ) time and space for every approach — the power set itself has 2ⁿ subsets, each up to length n
- Trap: forgetting to pop/backtrack after the "include" branch in the recursive version leaves stale values in the shared list for every later branch
Interview follow-ups
What if
numscould contain duplicate values, and the result shouldn't contain duplicate subsets (Subsets II)?Sort
numsfirst so equal values sit next to each other. Then, in the backtracking approach, skip starting a new "include" branch on a value equal to the previous one at the same recursion depth, unless that previous equal value was actually included on the current path. This prevents generating the same subset twice while still correctly allowing multiple copies of a repeated value to appear together within one subset.How would you generate only the subsets of a specific size k, instead of every subset?
This is exactly the "combinations" problem — the same include/exclude backtracking works, but the current subset is only appended to the result once its length reaches k. It can also be pruned earlier: stop exploring an "exclude" branch once there aren't enough elements left in
numsto possibly reach size k from here.
Frequently asked questions
Because the power set has exactly 2ⁿ subsets no matter how they're generated, and writing out each subset costs up to O(n). Producing the full answer therefore costs at least O(n · 2ⁿ) regardless of method — none of these three approaches beats that lower bound, they just differ in how they get there.
Because "optimal" here is about avoiding overhead the other two approaches carry, not about a better Big-O. The cascading approach repeatedly copies growing lists; the recursive approach carries function-call and stack overhead. The bitmask version is a flat loop with simple bit tests and no copying of intermediate collections, which tends to run measurably faster in practice even with an identical worst-case complexity.
Because current is one shared list reused across the entire recursion tree, not a fresh copy handed to each branch. Without popping the just-added value before trying the exclude branch, that branch would incorrectly still have the value sitting in it, corrupting every subsequent subset built from that point on.
Enumerating every possible on/off combination of a small set of options — which feature flags are enabled together, which subset of servers join a canary rollout, which permissions are granted together for an access-control test — is exactly generating a power set, and it's only practical while that set stays small (this problem's constraint caps nums at 10 elements for exactly that reason: 2¹⁰ is manageable, 2¹⁰⁰ isn't).