601. Every Subset
A smoothie bar keeps n different add-ins on a shelf. A customer may pick any group of add-ins, including no add-in at all, and each distinct group counts as one possible order. The array nums holds the code of every add-in; all codes are different.
Return every possible group as an array of codes. Each group must appear exactly once. The groups may be returned in any order, and the codes inside a group may be in any order too.
Aim for time proportional to the number of groups times their average size, O(n * 2^n).
Example 1
- Input:
- nums = [4,9]
- Output:
- [[],[9],[4],[4,9]]
- Explanation:
The four groups are the empty group,
[4],[9]and[4, 9].
Example 2
- Input:
- nums = []
- Output:
- [[]]
- Explanation:
With no add-ins the only group is the empty one.
Example 3
- Input:
- nums = [3,-2,7]
- Output:
- [[],[7],[-2],[-2,7],[3],[3,7],[3,-2],[3,-2,7]]
- Explanation:
Three add-ins give 2^3 = 8 groups, from the empty group up to
[3, -2, 7].
Constraints
- 0 ≤
nums.length≤ 8 - -10 ≤
nums[i]≤ 10 - All values of
numsare distinct.
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(n * 2^n)
- Space
- O(n)