Problem
Given an array of distinct integers, return every possible subset (the power set). The empty set and the full set both count. Subsets may be returned in any order, but none may repeat.
Worked examples
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Input: nums = [0]
Output: [[],[0]]
Hints
Hint 1
For each element there are exactly two options: include it or leave it out.
Hint 2
Recurse on the index, branching on that include/exclude choice.
Hint 3
Record the current path at every leaf (or at every node, if you loop over the next element to add).
Solution approach
- Walk the elements with a recursive function that holds the current partial subset. At index i, first recurse without nums[i], then push nums[i], recurse, and pop it back off. When i reaches the end, copy the current subset into the result. There are 2^n leaves and each copy costs up to n, which is optimal since that is the size of the output. An iterative alternative doubles the result list once per element.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n * 2^n) time; O(n) recursion, excluding output auxiliary space.
Report & practice notes
The candidate describes a subset task but says its examples were contradictory. This is a standard subsets practice version, not a reconstruction of the full assessment statement.
Read the candidate’s source report ↗