289. Every Selection by Mask
A pizza shop offers a list of distinct toppings, given as the integer array nums (each integer is a topping code). A customer may order any combination of toppings, including no topping at all and including every topping. Two orders are the same if they use the same toppings, regardless of the order in which the toppings are listed.
Return every possible order as a list of lists: all 2^n subsets of nums, each exactly once, with the empty subset included. The order of the subsets in the answer does not matter, and the order of the numbers inside a subset does not matter either; both are ignored when your answer is checked.
Represent each subset by a bitmask from 0 to 2^n - 1 and generate them in O(n * 2^n) time, which is optimal because that is the output size.
Example 1
- Input:
- nums = [8,-3]
- Output:
- [[],[8],[-3],[8,-3]]
- Explanation:
The 4 subsets of [8, -3] are listed (in any order), including the empty one.
Example 2
- Input:
- nums = [40,7,25]
- Output:
- [[],[40],[7],[40,7],[25],[40,25],[7,25],[40,7,25]]
- Explanation:
The 8 subsets of [40, 7, 25] are listed (in any order), including the empty one.
Example 3
- Input:
- nums = [99]
- Output:
- [[],[99]]
- Explanation:
The 2 subsets of [99] are listed (in any order), including the empty one.
Constraints
1 ≤ nums.length ≤ 10
-109 ≤ nums[i] ≤ 109
All values in nums are distinct.
Subset order and order within subsets are irrelevant.
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n * 2^n)
- Space
- O(n * 2^n)