Builds on Subsets, which you haven’t finished yet.
Bitmask Enumeration (Subset Masks)
A binary watch shows the time with 10 LEDs. Four LEDs on the top encode the hour (0 to 11) and six LEDs on the bottom encode the minute (0 to 59); each LED is one bit, with the lowest bit on the right.
Given turnedOn, the number of LEDs that are lit, return every time the watch could be showing, in any order. Write the hour without a leading zero ("1:00", never "01:00") and the minute with exactly two digits ("10:02", never "10:2").
Bitmask Subsets
collection ➔ integer mask ➔ subset statesn is small (roughly 20 or less) and you must try every subset, or a DP state is 'which items are used so far'.| 1 | def read_binary_watch(turnedOn: int) -> list[str]: |
| 2 | """Binary Watch: every set of lit LEDs is one 10-bit mask. |
| 3 | Time: O(B * 2^B), B = 10 LEDs | Space: O(1) extra, output not counted |
| 4 | """ |
| 5 | times: list[str] = [] # valid "h:mm" strings found so far |
| 6 | |
| 7 | # 1. Visit Every Possible Mask: |
| 8 | # Each integer 0 to 2^10 - 1 is one assignment of the 10 LEDs (4 hour bits, |
| 9 | # 6 minute bits), so looping over that range visits every combination once. |
| 10 | for mask in range(1 << 10): |
| 11 | if bin(mask).count("1") != turnedOn: # Popcount: how many LEDs are lit |
| 12 | continue |
| 13 | hour, minute = mask >> 6, mask & 0b111111 # Top 4 bits: hour; low 6 bits: minute |
| 14 | |
| 15 | # 2. Reject Out-Of-Range Fields: |
| 16 | # 4 bits can hold values up to 15 and 6 bits up to 63, but a watch only |
| 17 | # shows hours 0-11 and minutes 0-59, so a decoded field outside that range is dropped. |
| 18 | if hour < 12 and minute < 60: |
| 19 | times.append(f"{hour}:{minute:02d}") |
| 20 | return times |
| 21 | |
| 22 | |
| 23 | def subsets(nums: list[int]) -> list[list[int]]: |
| 24 | """Subsets: every subset of distinct nums, one bitmask per subset. |
| 25 | Time: O(N * 2^N) | Space: O(N * 2^N) output |
| 26 | """ |
| 27 | n = len(nums) |
| 28 | result: list[list[int]] = [] # one subset per mask |
| 29 | |
| 30 | # 1. Decode Each Mask Into Its Subset: |
| 31 | # Each integer 0 to 2^n - 1 is one subset; bit i of mask tells whether |
| 32 | # nums[i] is included, so collecting the items whose bit is on rebuilds that subset. |
| 33 | for mask in range(1 << n): |
| 34 | result.append([nums[i] for i in range(n) if (mask >> i) & 1]) |
| 35 | return result |
| 36 | |
| 37 | |
| 38 | def enumerate_submasks(mask: int) -> list[int]: |
| 39 | """Sub-Mask Enumeration: every subset of the bits set in `mask`, largest first. |
| 40 | Time: O(2^k), k = popcount(mask); O(3^n) summed over all masks | Space: O(2^k) output |
| 41 | """ |
| 42 | submasks: list[int] = [] # every non-empty submask found so far, largest first |
| 43 | sub = mask |
| 44 | |
| 45 | # 1. Step Through Every Non-Empty Submask: |
| 46 | # (sub - 1) & mask clears the lowest set bit of sub and sets every bit below |
| 47 | # it, then masking with mask drops anything outside it, landing on the next smaller submask. |
| 48 | while sub > 0: |
| 49 | submasks.append(sub) |
| 50 | sub = (sub - 1) & mask # Drop the lowest bit, keep only bits inside mask |
| 51 | |
| 52 | # 2. Add the Empty Set: |
| 53 | # The loop above stops once sub reaches 0, so the empty submask is never |
| 54 | # appended inside it; add it once here. |
| 55 | submasks.append(0) |
| 56 | return submasks |
i of mask is on exactly when item i is in the subset, so each number in range(1 << n) is one subset and every subset appears once.An integer is a set: bit i is on when item i is chosen, so the subsets of n items are exactly the numbers in range(1 << n), (mask >> i) & 1 says whether item i is in, and bin(mask).count("1") how many items are. Each subset matches one number and each number one subset, so one loop visits every subset exactly once, with no recursion and no duplicates; to visit only the subsets of one mask, step with sub = (sub - 1) & mask, which clears the lowest set bit, sets the bits below it, and keeps only bits of mask. The trap is decoding a packed mask: split it into its fields (hour = mask >> 6, minute = mask & 0b111111) and check each field's range (hour < 12 and minute < 60), because 4 bits reach 15 and 6 bits reach 63.
See it run
Subsets of nums = [1, 2, 3] with one mask per subset
n 3masks 8
Each column is one mask, from 0 up. The top row is the mask in binary, and the last digit is bit 0. This board replays Subsets (LeetCode 78), while the step debugger opens on Binary Watch (LeetCode 401), the other problem of this card.
maskthe mask being readsubsetthe subset built from that mask
There are 3 items, so range(1 << 3) gives 8 masks, 0 to 7. Each mask is one subset.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out the check
hour < 12 and minute < 60Mistaketimes.append(f"{hour}:{minute:02d}")Fixif hour < 12 and minute < 60: times.append(f"{hour}:{minute:02d}")What happens: The hour field has 4 bits, so it can hold values up to 15. The minute field has 6 bits, so it can hold values up to 63. A watch shows only hours 0 to 11 and minutes 0 to 59. Without the check, masks such as
15:63are added as times.Example: turnedOn = 10Mistake: returns ['15:63']Fix: returns []
- The input has repeated values and each distinct subset may appear only once, as in Subsets II (LC 90): two different masks can build the same subset. See Subsets II
- The best answer for one set of used items is needed again by many larger sets, as in Partition to K Equal Sum Subsets (LC 698): trying each subset on its own repeats that work. See Bitmask DP
Deep Dive
Why each integer is exactly one subset
An integer with n bits is a row of n on-or-off switches. Bit i of mask is on exactly when item i is in the subset. This is the card's invariant.
There are 2^n different bit patterns of length n, and range(1 << n) lists all of them once. There are also 2^n subsets of n items, because each item is either in or out. The two lists match one to one, so the loop visits every subset once and never repeats one.
In Subsets (LC 78) with nums = [1, 2, 3], the masks 0 to 7 build [], [1], [2], [1, 2], [3], [1, 3], [2, 3] and [1, 2, 3]. For example, mask = 5 is 0b101, so bits 0 and 2 are on, and the subset is [1, 3].
The three basic operations
To test whether item i is in mask, use (mask >> i) & 1. The shift >> i moves bit i to the lowest position. The & 1 keeps only that bit.
To count the items in mask, use bin(mask).count("1"). This count is called the popcount, the number of bits that are 1. read_binary_watch uses it to keep only the masks with turnedOn lit LEDs.
Bits are numbered from 0. Testing (mask >> (i + 1)) & 1 for item i reads the next item instead, so item 0 is never chosen.
Packed fields and sub-masks
A mask can hold several fields side by side. In Binary Watch (LC 401), the top 4 bits are the hour and the low 6 bits are the minute. mask >> 6 gives the hour, and mask & 0b111111 gives the minute.
Each field can hold more values than the problem allows. Four bits reach 15 and six bits reach 63, but a watch shows hours 0 to 11 and minutes 0 to 59. So read_binary_watch checks hour < 12 and minute < 60.
To visit only the subsets of one mask, enumerate_submasks steps with sub = (sub - 1) & mask. Subtracting 1 clears the lowest set bit and sets every bit below it. The & mask removes the bits that are not in mask. The next value is the next smaller sub-mask. For mask = 0b1101, the sequence is 13, 12, 9, 8, 5, 4, 1, and then 0.
The loop while sub > 0 stops before 0, so the empty sub-mask must be added after the loop.
The cost: 2^n masks times work per mask
subsets creates 2^N masks, and each one builds a list in O(N) time. The total is O(N * 2^N) time. The output holds up to N * 2^N numbers, so the space is also O(N * 2^N).
read_binary_watch has B = 10 bits. It visits 1024 masks and counts the bits of each one. This is why the card writes O(B * 2^B). The result is small: 10 times for one lit LED and 44 times for two.
enumerate_submasks returns 2^k values for a mask with k bits on. Summed over all masks of n bits, the total is 3^n. For n = 1 to 8, the totals are 3, 9, 27, 81, 243, 729, 2187 and 6561. Each item is in one of three states: outside mask, in mask but not in the sub-mask, or in both.
This is why the card's trigger says n is about 20 or less. With n = 20 there are 1,048,576 masks. Each extra item doubles that number.
60-Second Pitch
"With n up to about 20, I can try every subset. I represent a subset as an integer mask, where bit i is on when item i is chosen. The integers from 0 to 2^n - 1 match the subsets one to one. So one loop over range(1 << n) visits every subset once, with no recursion and no duplicates. To test an item, I use (mask >> i) & 1. To build the subset, I collect the items with a bit on. The cost is 2^n masks and O(n) work for each, so O(n * 2^n) time. If I only need to visit the subsets of one mask, I step with sub = (sub - 1) & mask, and I add the empty set after the loop."
Common Questions
- Why does
range(1 << n)visit every subset exactly once? Each integer from 0 to 2^n - 1 has a different pattern of
nbits. Each pattern says, for every item, whether it is in or out. There are 2^n such patterns and 2^n subsets, and each pattern maps to one subset. So no subset is repeated and none is missed.- How is this different from the recursive approach in Subsets (LC 78)?
Both produce all 2^N subsets in O(N * 2^N) time. The recursive Take or Skip approach builds a
pathand undoes each choice. The mask loop has no recursion and no undo step. The recursive approach is easier to extend with pruning or with a rule for duplicate values.- How do you iterate over the subsets of a given mask?
Start with
sub = mask. Processsub, then setsub = (sub - 1) & mask. The subtraction clears the lowest set bit and sets the bits below it. The& maskremoves bits that are outsidemask. Stop whensubis 0, and handle the empty set separately.- What is the cost of visiting all sub-masks of all masks?
It is O(3^n). Each of the
nitems is in one of three states: outside the mask, in the mask but not in the sub-mask, or in both. Forn = 8, the total is 6561.- When is a bitmask the wrong tool?
When
nis above about 20, because the loop needs 2^n steps. It is also the wrong tool when the input has repeated values and each subset must appear once, because different masks then build the same subset. In both cases use another method, such as the Take or Skip card with a skip rule.
SWE Reasoning
Spot it
nis small, roughly 20 or less, and the task is to try every subset.- A DP state is which items are used so far, so the state itself can be one integer.
- The problem has a few fixed on-or-off switches, such as the LEDs in Binary Watch (LC 401).
- You need all subsets in a flat loop, with no recursion and no
pathlist to undo. - The input has distinct items. If values repeat, as in Subsets II (LC 90), two masks can build the same subset.
The invariant, step by step
masktakes each value from 0 to(1 << n) - 1, one value per loop step.- Bit
iofmaskis on exactly when itemiis in the subset. (mask >> i) & 1reads biti, and the list comprehension collects thenums[i]whose bit is on. This rebuilds the subset.- Different masks differ in at least one bit, so they differ in at least one item. No subset is built twice.
- Every choice of in-or-out for the
nitems is one bit pattern, and that pattern is in the range. No subset is missed. - For sub-masks,
sub = (sub - 1) & maskalways moves to the next smaller value whose bits are all insidemask. It starts atmaskand ends after 0 is reached.
Traps
- Skip the range check on a packed mask. Without
hour < 12 and minute < 60,read_binary_watch(10)returns['15:63']instead of[]. - Write the minute without
:02d. The time becomes'0:1'instead of'0:01'. - Test bit
i + 1for itemi. Item 0 is never chosen. For[1, 2], the result is[[], [], [1], [1]]instead of[[], [1], [2], [1, 2]]. - Forget the empty sub-mask. The loop
while sub > 0never appends 0. Formask = 0b101, the result is[5, 4, 1]instead of[5, 4, 1, 0]. - Use the card when
nis large. The loop has 2^n steps. Atn = 40it cannot finish. Check the constraint onnbefore choosing it. - Duplicate values in the input. Two different masks can build the same subset. Subsets II (LC 90) needs sorting and a skip rule, as the Take or Skip card shows.
Practice
Builds on Subsets, which you haven’t finished yet.
Bitmask Enumeration (Subset Masks)
A binary watch shows the time with 10 LEDs. Four LEDs on the top encode the hour (0 to 11) and six LEDs on the bottom encode the minute (0 to 59); each LED is one bit, with the lowest bit on the right.
Given turnedOn, the number of LEDs that are lit, return every time the watch could be showing, in any order. Write the hour without a leading zero ("1:00", never "01:00") and the minute with exactly two digits ("10:02", never "10:2").
Bitmask Subsets
collection ➔ integer mask ➔ subset statesn is small (roughly 20 or less) and you must try every subset, or a DP state is 'which items are used so far'.| 1 | def read_binary_watch(turnedOn: int) -> list[str]: |
| 2 | """Binary Watch: every set of lit LEDs is one 10-bit mask. |
| 3 | Time: O(B * 2^B), B = 10 LEDs | Space: O(1) extra, output not counted |
| 4 | """ |
| 5 | times: list[str] = [] # valid "h:mm" strings found so far |
| 6 | |
| 7 | # 1. Visit Every Possible Mask: |
| 8 | # Each integer 0 to 2^10 - 1 is one assignment of the 10 LEDs (4 hour bits, |
| 9 | # 6 minute bits), so looping over that range visits every combination once. |
| 10 | for mask in range(1 << 10): |
| 11 | if bin(mask).count("1") != turnedOn: # Popcount: how many LEDs are lit |
| 12 | continue |
| 13 | hour, minute = mask >> 6, mask & 0b111111 # Top 4 bits: hour; low 6 bits: minute |
| 14 | |
| 15 | # 2. Reject Out-Of-Range Fields: |
| 16 | # 4 bits can hold values up to 15 and 6 bits up to 63, but a watch only |
| 17 | # shows hours 0-11 and minutes 0-59, so a decoded field outside that range is dropped. |
| 18 | if hour < 12 and minute < 60: |
| 19 | times.append(f"{hour}:{minute:02d}") |
| 20 | return times |
| 21 | |
| 22 | |
| 23 | def subsets(nums: list[int]) -> list[list[int]]: |
| 24 | """Subsets: every subset of distinct nums, one bitmask per subset. |
| 25 | Time: O(N * 2^N) | Space: O(N * 2^N) output |
| 26 | """ |
| 27 | n = len(nums) |
| 28 | result: list[list[int]] = [] # one subset per mask |
| 29 | |
| 30 | # 1. Decode Each Mask Into Its Subset: |
| 31 | # Each integer 0 to 2^n - 1 is one subset; bit i of mask tells whether |
| 32 | # nums[i] is included, so collecting the items whose bit is on rebuilds that subset. |
| 33 | for mask in range(1 << n): |
| 34 | result.append([nums[i] for i in range(n) if (mask >> i) & 1]) |
| 35 | return result |
| 36 | |
| 37 | |
| 38 | def enumerate_submasks(mask: int) -> list[int]: |
| 39 | """Sub-Mask Enumeration: every subset of the bits set in `mask`, largest first. |
| 40 | Time: O(2^k), k = popcount(mask); O(3^n) summed over all masks | Space: O(2^k) output |
| 41 | """ |
| 42 | submasks: list[int] = [] # every non-empty submask found so far, largest first |
| 43 | sub = mask |
| 44 | |
| 45 | # 1. Step Through Every Non-Empty Submask: |
| 46 | # (sub - 1) & mask clears the lowest set bit of sub and sets every bit below |
| 47 | # it, then masking with mask drops anything outside it, landing on the next smaller submask. |
| 48 | while sub > 0: |
| 49 | submasks.append(sub) |
| 50 | sub = (sub - 1) & mask # Drop the lowest bit, keep only bits inside mask |
| 51 | |
| 52 | # 2. Add the Empty Set: |
| 53 | # The loop above stops once sub reaches 0, so the empty submask is never |
| 54 | # appended inside it; add it once here. |
| 55 | submasks.append(0) |
| 56 | return submasks |
i of mask is on exactly when item i is in the subset, so each number in range(1 << n) is one subset and every subset appears once.An integer is a set: bit i is on when item i is chosen, so the subsets of n items are exactly the numbers in range(1 << n), (mask >> i) & 1 says whether item i is in, and bin(mask).count("1") how many items are. Each subset matches one number and each number one subset, so one loop visits every subset exactly once, with no recursion and no duplicates; to visit only the subsets of one mask, step with sub = (sub - 1) & mask, which clears the lowest set bit, sets the bits below it, and keeps only bits of mask. The trap is decoding a packed mask: split it into its fields (hour = mask >> 6, minute = mask & 0b111111) and check each field's range (hour < 12 and minute < 60), because 4 bits reach 15 and 6 bits reach 63.
See it run
Subsets of nums = [1, 2, 3] with one mask per subset
n 3masks 8
Each column is one mask, from 0 up. The top row is the mask in binary, and the last digit is bit 0. This board replays Subsets (LeetCode 78), while the step debugger opens on Binary Watch (LeetCode 401), the other problem of this card.
maskthe mask being readsubsetthe subset built from that mask
There are 3 items, so range(1 << 3) gives 8 masks, 0 to 7. Each mask is one subset.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out the check
hour < 12 and minute < 60Mistaketimes.append(f"{hour}:{minute:02d}")Fixif hour < 12 and minute < 60: times.append(f"{hour}:{minute:02d}")What happens: The hour field has 4 bits, so it can hold values up to 15. The minute field has 6 bits, so it can hold values up to 63. A watch shows only hours 0 to 11 and minutes 0 to 59. Without the check, masks such as
15:63are added as times.Example: turnedOn = 10Mistake: returns ['15:63']Fix: returns []
- The input has repeated values and each distinct subset may appear only once, as in Subsets II (LC 90): two different masks can build the same subset. See Subsets II
- The best answer for one set of used items is needed again by many larger sets, as in Partition to K Equal Sum Subsets (LC 698): trying each subset on its own repeats that work. See Bitmask DP
Deep Dive
Why each integer is exactly one subset
An integer with n bits is a row of n on-or-off switches. Bit i of mask is on exactly when item i is in the subset. This is the card's invariant.
There are 2^n different bit patterns of length n, and range(1 << n) lists all of them once. There are also 2^n subsets of n items, because each item is either in or out. The two lists match one to one, so the loop visits every subset once and never repeats one.
In Subsets (LC 78) with nums = [1, 2, 3], the masks 0 to 7 build [], [1], [2], [1, 2], [3], [1, 3], [2, 3] and [1, 2, 3]. For example, mask = 5 is 0b101, so bits 0 and 2 are on, and the subset is [1, 3].
The three basic operations
To test whether item i is in mask, use (mask >> i) & 1. The shift >> i moves bit i to the lowest position. The & 1 keeps only that bit.
To count the items in mask, use bin(mask).count("1"). This count is called the popcount, the number of bits that are 1. read_binary_watch uses it to keep only the masks with turnedOn lit LEDs.
Bits are numbered from 0. Testing (mask >> (i + 1)) & 1 for item i reads the next item instead, so item 0 is never chosen.
Packed fields and sub-masks
A mask can hold several fields side by side. In Binary Watch (LC 401), the top 4 bits are the hour and the low 6 bits are the minute. mask >> 6 gives the hour, and mask & 0b111111 gives the minute.
Each field can hold more values than the problem allows. Four bits reach 15 and six bits reach 63, but a watch shows hours 0 to 11 and minutes 0 to 59. So read_binary_watch checks hour < 12 and minute < 60.
To visit only the subsets of one mask, enumerate_submasks steps with sub = (sub - 1) & mask. Subtracting 1 clears the lowest set bit and sets every bit below it. The & mask removes the bits that are not in mask. The next value is the next smaller sub-mask. For mask = 0b1101, the sequence is 13, 12, 9, 8, 5, 4, 1, and then 0.
The loop while sub > 0 stops before 0, so the empty sub-mask must be added after the loop.
The cost: 2^n masks times work per mask
subsets creates 2^N masks, and each one builds a list in O(N) time. The total is O(N * 2^N) time. The output holds up to N * 2^N numbers, so the space is also O(N * 2^N).
read_binary_watch has B = 10 bits. It visits 1024 masks and counts the bits of each one. This is why the card writes O(B * 2^B). The result is small: 10 times for one lit LED and 44 times for two.
enumerate_submasks returns 2^k values for a mask with k bits on. Summed over all masks of n bits, the total is 3^n. For n = 1 to 8, the totals are 3, 9, 27, 81, 243, 729, 2187 and 6561. Each item is in one of three states: outside mask, in mask but not in the sub-mask, or in both.
This is why the card's trigger says n is about 20 or less. With n = 20 there are 1,048,576 masks. Each extra item doubles that number.
60-Second Pitch
"With n up to about 20, I can try every subset. I represent a subset as an integer mask, where bit i is on when item i is chosen. The integers from 0 to 2^n - 1 match the subsets one to one. So one loop over range(1 << n) visits every subset once, with no recursion and no duplicates. To test an item, I use (mask >> i) & 1. To build the subset, I collect the items with a bit on. The cost is 2^n masks and O(n) work for each, so O(n * 2^n) time. If I only need to visit the subsets of one mask, I step with sub = (sub - 1) & mask, and I add the empty set after the loop."
Common Questions
- Why does
range(1 << n)visit every subset exactly once? Each integer from 0 to 2^n - 1 has a different pattern of
nbits. Each pattern says, for every item, whether it is in or out. There are 2^n such patterns and 2^n subsets, and each pattern maps to one subset. So no subset is repeated and none is missed.- How is this different from the recursive approach in Subsets (LC 78)?
Both produce all 2^N subsets in O(N * 2^N) time. The recursive Take or Skip approach builds a
pathand undoes each choice. The mask loop has no recursion and no undo step. The recursive approach is easier to extend with pruning or with a rule for duplicate values.- How do you iterate over the subsets of a given mask?
Start with
sub = mask. Processsub, then setsub = (sub - 1) & mask. The subtraction clears the lowest set bit and sets the bits below it. The& maskremoves bits that are outsidemask. Stop whensubis 0, and handle the empty set separately.- What is the cost of visiting all sub-masks of all masks?
It is O(3^n). Each of the
nitems is in one of three states: outside the mask, in the mask but not in the sub-mask, or in both. Forn = 8, the total is 6561.- When is a bitmask the wrong tool?
When
nis above about 20, because the loop needs 2^n steps. It is also the wrong tool when the input has repeated values and each subset must appear once, because different masks then build the same subset. In both cases use another method, such as the Take or Skip card with a skip rule.
SWE Reasoning
Spot it
nis small, roughly 20 or less, and the task is to try every subset.- A DP state is which items are used so far, so the state itself can be one integer.
- The problem has a few fixed on-or-off switches, such as the LEDs in Binary Watch (LC 401).
- You need all subsets in a flat loop, with no recursion and no
pathlist to undo. - The input has distinct items. If values repeat, as in Subsets II (LC 90), two masks can build the same subset.
The invariant, step by step
masktakes each value from 0 to(1 << n) - 1, one value per loop step.- Bit
iofmaskis on exactly when itemiis in the subset. (mask >> i) & 1reads biti, and the list comprehension collects thenums[i]whose bit is on. This rebuilds the subset.- Different masks differ in at least one bit, so they differ in at least one item. No subset is built twice.
- Every choice of in-or-out for the
nitems is one bit pattern, and that pattern is in the range. No subset is missed. - For sub-masks,
sub = (sub - 1) & maskalways moves to the next smaller value whose bits are all insidemask. It starts atmaskand ends after 0 is reached.
Traps
- Skip the range check on a packed mask. Without
hour < 12 and minute < 60,read_binary_watch(10)returns['15:63']instead of[]. - Write the minute without
:02d. The time becomes'0:1'instead of'0:01'. - Test bit
i + 1for itemi. Item 0 is never chosen. For[1, 2], the result is[[], [], [1], [1]]instead of[[], [1], [2], [1, 2]]. - Forget the empty sub-mask. The loop
while sub > 0never appends 0. Formask = 0b101, the result is[5, 4, 1]instead of[5, 4, 1, 0]. - Use the card when
nis large. The loop has 2^n steps. Atn = 40it cannot finish. Check the constraint onnbefore choosing it. - Duplicate values in the input. Two different masks can build the same subset. Subsets II (LC 90) needs sorting and a skip rule, as the Take or Skip card shows.