medium
Subsets
Given an array of distinct integers, return every possible subset (the power set), in any order.
Constraints
- 1 ≤ n ≤ 10
- All elements distinct
Examples
in: nums = [1,2,3]
out: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Recognition clues
- Output size is 2^n — must enumerate
- Each element is either taken or skipped
- Build partial answers and undo choices
Pattern
BacktrackingEnumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.
Solution
Recurse over the index with a current partial subset. At each index, either skip the element or include it, recurse, then remove it (backtrack). When the index reaches n, record a copy of the current subset. The recursion tree has exactly 2^n leaves, one per subset.
time O(n · 2^n)space O(n) recursion depth
Alternative approaches
- Iterate masks from 0 to 2^n − 1 and take element
iwhen bitiis set — no recursion needed. Iteratively doubling a list by appending the next element to each existing subset also works.
Code it yourself
Solve in
Hints: