You are given an array of integers nums in which every element is unique. Return every possible subset of nums — the power set.
A subset is any selection of elements from the array: the empty selection counts, and so does the whole array. Your answer must not contain duplicate subsets, and you may return the subsets — and the elements inside each subset — in any order.
n elements is independently in or out — two choices per element, so 2 × 2 × … × 2 = 2^n combinations. The empty set (all out) and the full array (all in) are both included.[] in the answer.path is a single shared list that keeps mutating as the recursion unwinds. If you store a reference to it, every saved subset later points at the same, finally-empty list. Snapshot with path[:] (Python), a spread (JavaScript), or an explicit copy (Go).k, and stop descending when even taking every remaining element cannot reach k.0 to 2^n − 1 and read each one as an in/out vector).Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Every combination of the three elements appears exactly once — 2^3 = 8 subsets, from the empty set to the full array.
Input: nums = [0] Output: [[],[0]] One element gives 2^1 = 2 subsets: leave it out, or take it.
- 1 <= nums.length <= 10 - -10 <= nums[i] <= 10 - All elements of nums are unique.
Generating every subset — the power set — is the doorway to backtracking. The pick-or-skip decision tree you build here is the exact skeleton behind Combination Sum, Permutations, and Word Search; master it once and a whole family of problems becomes variations on a theme.
n independent bits — it unlocks the elegant bitmask approach.In plain English: given nums, whose elements are all distinct, return every selection of its elements — from selecting nothing to selecting everything. With n elements there are exactly 2^n selections. Both the order of subsets and the order of elements inside a subset are up to you.
Worked example — nums = [1,2]
decide about 1
/ \
skip 1 pick 1
| |
decide about 2 decide about 2
/ \ / \
skip 2 pick 2 skip 2 pick 2
[] [2] [1] [1,2]
Four leaves, four subsets — 2^2 = 4. For nums = [1,2,3] the tree grows one level deeper and yields 2^3 = 8 subsets, matching Example 1.
Asking two or three sharp questions before coding shows you think about contracts, not just code.
“Are all elements guaranteed to be distinct?”
Yes — so no two generated subsets can ever collide, and no dedup step is needed. With duplicates allowed, the problem becomes Subsets II, which needs sorting plus skip-the-repeat logic.
“Can the array be empty?”
No — there is at least one element. A clean recursion handles the empty case for free anyway: it would return just the empty subset.
“Does the order of subsets, or of elements inside a subset, matter?”
No — any order is accepted. That frees you to emit subsets in whatever order your traversal naturally produces.
“Should the empty subset be included?”
Yes — the power set always contains both the empty set and the full set.
“How large can the array get?”
Only 10 elements — so at most 2^10 = 1024 subsets. The output is exponential by definition, so an O(n · 2^n) algorithm is not a compromise; it is optimal.
Before I code, let me confirm the guarantees.
All elements are distinct, so I never need to worry about duplicate subsets appearing.
Since n is at most ten, the full power set is only about a thousand subsets — the output is exponential by nature, and I will generate it with a pick-or-skip recursion.
For each element you decide: in or out. The decisions are independent, so the total count is 2 × 2 × … × 2 = 2^n. Any procedure that enumerates every decision row enumerates every subset exactly once — because elements are unique, no deduplication is ever needed.
Level i decides nums[i]: branch one way to skip it, the other way to pick it. Every leaf is one complete subset. Walk the tree depth-first carrying a shared path: append on pick, pop on the way back. That append/undo pair is backtracking.
level 0 skip 1 ──────────── pick 1 level 1 skip 2 pick 2 skip 2 pick 2 leaves [] [2] [1] [1,2]
There are 2^n subsets with an average length of n/2, so just writing the answer down costs about n · 2^(n-1) integers. Every correct algorithm is output-bound. All three approaches below share the same complexity; they differ in mechanism and in what they teach you.
All three approaches run in O(n · 2^n) — the output size dictates it. What differs is the machinery:
| Cascading | Bit masks | Backtracking | |
|---|---|---|---|
| Time | O(n · 2^n) | O(n · 2^n) | O(n · 2^n) |
| Extra space | copies at every step | O(n) per subset | O(n) recursion depth |
| Style | iterative doubling | counting in binary | decision-tree DFS |
Full code for each lives in the Approaches selector below. The backtracking version is the one to internalize — it is the template for the entire backtracking family.
Key takeaway
Enumerating subsets means walking a binary decision tree: at index i, branch on skip nums[i] versus pick nums[i], record a copy of the path at the bottom, and undo the pick as you return. This pick-or-skip skeleton — plus pruning — powers the whole backtracking family.
backtrack(i, path): if i == n: record a COPY of path; return backtrack(i + 1, path) # skip nums[i] path.push(nums[i]) # pick nums[i] backtrack(i + 1, path) path.pop() # undo — leave path as you found it backtrack(0, [])