Topic · BacktrackingMedium
Subsets
Understand the problem
Given an array of distinct integers nums, return all possible subsets (the power set) — including the empty set and the set itself.
Example:
ts
nums = [1, 2, 3]
output = [
[], [1], [2], [3],
[1,2], [1,3], [2,3],
[1,2,3]
]
// 2³ = 8 subsets (n elements → 2ⁿ subsets)
nums = [0]
output = [[], [0]]Every element has 2 choices: include it or not.
Backtracking enumerates all 2ⁿ branches.
Basic approach
O(n × 2ⁿ) time, O(n) auxiliary space (not counting the output) — 2ⁿ subsets, each takes O(n) to buildts
// Bit masking — a binary number represents each subset
function subsetsBitmask(nums: number[]): number[][] {
const n = nums.length
const result: number[][] = []
for (let mask = 0; mask < (1 << n); mask++) {
const subset: number[] = []
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) subset.push(nums[i])
}
result.push(subset)
}
return result
}Why this approach is slow:
Bit masking is another way to generate the 2ⁿ subsets.
- Backtracking is more natural and extends more easily to variants (subsets with duplicates, subset sum).
- Both have the same Big-O.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.