Subsets
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.
Examples
Constraints
- • 1 <= nums.length <= 10
- • All elements are distinct
Hints & approach
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).
Approachtry the hints first
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.
Time O(n * 2^n) · Space O(n) recursion, excluding output