Bit Manipulation Bitmasks
122. Subsets in Binary Order
You are given an array nums of n integers, all different from each other. Return all 2n
subsets of nums, in the order described below. A subset is any selection of elements, from none of them
to all of them.
Number the subsets from 0 to 2n − 1. Subset number m holds nums[i] exactly when the binary digit
of m worth 2i is 1. So subset 0 is empty, subset 1 holds only nums[0], subset 2 holds only
nums[1], subset 3 holds nums[0] and nums[1], and subset 2n − 1 holds every element.
Return the subsets in the order of their numbers, from 0 up. Inside each subset, list the values in the order
they appear in nums. So there is exactly one right answer.
Example 1
Input: nums = [4, -1, 9]
[[],[4],[-1],[4,-1],[9],[4,9],[-1,9],[4,-1,9]]Explanation: There are 23 = 8 subsets. Subset 5 is 101 in binary: its digits worth 1 and 4 are set, so it
holds nums[0] = 4 and nums[2] = 9, and it comes sixth, after subsets 0 to 4.
Example 2
Input: nums = [7]
[[],[7]]Explanation: One element gives two subsets. Subset 0 is the empty one, and subset 1 holds the 7.
Example 3
Input: nums = [1000000000, -1000000000]
[[],
[1000000000],
[-1000000000],
[1000000000,-1000000000]]Explanation: The values reach both ends of their range. The last subset keeps the order of nums, so 1000000000 comes
before −1000000000 even though it is larger.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 16-109 ≤ nums[i] ≤ 109- All the values in
numsare different.
Clarifying questions
What you would ask an interviewer before writing any code.