1270. Every Submask of a Mask
A mask m over n items is given. A SUBMASK of m is any mask whose set bits
are all set in m as well, which is the same as saying s & m == s. Print
every submask of m in DESCENDING order, starting at m itself and ending
at 0.
n=3 m=5 = 101 -> 5 4 1 0
n=4 m=10 = 1010 -> 10 8 2 0
n=3 m=0 -> 0
## What most people try first
Loop t from m down to 0 and keep the values with t & m == t. It is
correct and it visits m + 1 candidates to find 2^popcount(m) answers. For
m = 1048575 with 20 bits that is a million candidates and a million answers,
so nothing is wasted. For m = 524289, which has two bits, it is still a
million candidates to find FOUR answers: a quarter of a million wasted tests
each.
The wasted work grows with the WIDTH while the answer count grows with the POPCOUNT, and those are unrelated.
## The loop that skips straight to the next one
s = m
loop forever:
report s
if s == 0: stop
s = (s - 1) & m
Why (s - 1) & m lands exactly on the next submask down, with nothing skipped
and nothing visited twice:
s - 1 clears s's lowest set bit and sets every bit below it, as #1251
argues. ANDing with m then restricts those newly set low bits to the ones
m actually has. The result is therefore the largest value that is both a
submask of m and strictly less than s: everything above the changed
position is untouched, the changed position went from 1 to 0, and below it
every available bit of m has been turned on, which is the largest possible
tail.
Because each step produces the immediate predecessor among submasks, the enumeration is complete and in strictly descending order.
## Why the exit test cannot be the loop condition
(0 - 1) & m is m again, since 0 - 1 is all ones. So a loop written
while (s) { report s; s = (s-1) & m; } never reports 0, and a loop written
do { s = (s-1) & m; report s; } while (s) runs forever once it reaches 0. The
only shapes that work report s first and then break ON zero rather than
testing zero at the top. That is the single most common mistake in this pattern
and it is why 0 is in the required output.
## Width
n is at most 20, so every mask is at most 1048575 and fits in a signed
32-bit integer, limit 2147483647, with ten bits to spare. JavaScript's & and
- are safe on plain Numbers here, because every value involved already fits
in signed 32 bits. No 64-bit type and no BigInt is needed anywhere in this
problem.
Constraints - `1 ≤ n ≤ 20` - `0 ≤ m ≤ 2^n - 1` - `m` has at most 10 set bits, so at most 1024 submasks are printed
Input
A single line containing two integers n and m, separated by a space.
Output
Print all submasks of m on one line, in strictly descending order, separated by single spaces. The first value printed is m and the last is always 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.