Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Subsets — and the elements within each subset — may be returned in any order.
Example
All 2^3 = 8 subsets, including the empty set.
Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All numbers are unique.
Intuition
The most direct way to enumerate every subset is to walk the decision tree by hand: at each number, either include it in the subset being built or leave it out, then recurse into the rest of the array. When the recursion runs out of numbers, the path built so far is one complete subset.
function subsets(nums) {
const result = [];
const path = []; // the subset currently being built
function backtrack(i) {
// Base case: a decision has been made for every index — record a copy of the path.
if (i === nums.length) {
result.push([...path]);
return;
}
// Choice 1: include nums[i], recurse into the rest, then undo (pop) before trying the other choice.
path.push(nums[i]);
backtrack(i + 1);
path.pop();
// Choice 2: leave nums[i] out entirely, recurse with the same (unchanged) path.
backtrack(i + 1);
}
backtrack(0);
return result;
}This already runs in O(n · 2ⁿ) — the same order as the optimal solution, since the output itself holds 2ⁿ subsets of up to length n to copy, so there's no asymptotic time left to shave off. Can we do better?
Not on complexity — but on how directly the choices get made. Look at what happens to the whole collection of subsets built so far each time a new number arrives: every existing subset either stays as it is (exclude), or gets a copy with the new number appended (include). That's the exact include/exclude decision the recursion above makes one leaf at a time, just applied to an entire generation of subsets at once. It's also the same building block behind Bit manipulation's enumeration trick — each subset is one n-bit mask, one bit per index, where a set bit means "included".
The stored solution takes that doubling route: start from the single empty subset [[]], and for each number, extend a copy of every subset built so far with it, doubling the collection each step. Bridging the two models: after processing the first k numbers, result holds exactly the 2^k leaves the recursion above would reach after deciding on those k indices — the line result.concat(result.map(sub => [...sub, num])) is the include/exclude branch from the walkthrough below, applied to every one of those leaves simultaneously instead of one root-to-leaf path at a time.
Walking it through:
nums = [2, 5, 8]
Start at index 0 with an empty path. Try the include branch first: choose 2.
One level deeper. `marked` here means "already chosen", not "discarded" — 2 is locked into the path.
All three included — a leaf. Record a copy of the path: [2, 5, 8].
Backtrack: pop 8 back off, then take the skip branch at the same depth. That's also a complete subset — record [2, 5].
Unwind one more level, pop 5, and take skip at index 1. The subtree under "5 excluded" still needs exploring for 8.
Finally pop 2 and take skip at the root. The mirrored subtree (2 excluded) produces the remaining subsets the same way — after the full traversal, all 2³ = 8 subsets have been recorded.
Optimization
Iterative expansion
Start from the single empty subset. For each number, append it to copies of every subset built so far, doubling the collection. After processing all numbers you have the full power set.
O(n · 2^n) time and output size, O(1) extra beyond the result.
function subsets(nums) {
// Start with just the empty subset.
let result = [[]];
for (const num of nums) {
// Every existing subset either stays as-is (already in result) or gets num appended —
// concatenate the two, doubling the collection each pass.
result = result.concat(result.map((sub) => [...sub, num]));
}
return result;
}Complexity analysis
Time complexity: O(n · 2ⁿ). Here's why:
- The result doubles once per number: after processing
kof thennumbers it holds2^ksubsets, so after allnnumbers it holds2ⁿsubsets total. - Each doubling step maps over the current result, copying every existing subset (up to length
n) to append the new number — one copy costs up to O(n). - Summed across all
ndoubling steps, the total work tracks the combined size of every subset ever built.
So the overall time is O(n · 2ⁿ) — which is also the size of the output itself, so no algorithm that returns every subset can do better.
Space complexity: O(n · 2ⁿ). Here's why:
- The final
resultholds all2ⁿsubsets; each of thennumbers appears in exactly half of them, so the combined length across every subset isn · 2ⁿ⁻¹. result.concat(...)and.map(...)allocate new arrays each step, but those become the final subsets rather than adding overhead beyond them.- The approach is iterative, not recursive, so there's no call stack to add on top.
So the extra space is O(n · 2ⁿ), dominated by the output — the same size the problem forces any solution to produce.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [9] | [[],[9]] | Single positive element — smallest possible input, 2¹ = 2 subsets. |
| nums = [-8,4] | [[],[-8],[4],[-8,4]] | Two elements, one negative — 2² = 4 subsets. |
| nums = [3,-3,6] | [[],[3],[-3],[3,-3],[6],[3,6],[-3,6],[3,-3,6]] | Three elements including a negative — 2³ = 8 subsets, in the order the doubling actually builds them. |
| nums = [0,-5,10,2] | [[],[0],[-5],[0,-5],[10],[0,10],[-5,10],[0,-5,10],[2],[0,2],[-5,2],[0,-5,2],[10,2],[0,10,2],[-5,10,2],[0,-5,10,2]] | Four elements spanning zero and both signs — 2⁴ = 16 subsets, checks the doubling scales past one round. |
| nums = [-7,1] | [[],[-7],[1],[-7,1]] | Two elements, both boundary-adjacent signs — a second pair case distinct from row 2. |
Try it yourself
Write your solution against the real judge before checking the reference.