1232. Every Subset, One Change at a Time

There are n items numbered 1 to n. Print all 2^n subsets, one per line, in this order:

> Line i, counting from 0, holds the subset in which item j is present > exactly when bit j - 1 of the number i XOR (i >> 1) is 1.

Print the members of each subset in increasing order separated by single spaces, and the word empty for the empty subset.

n = 3 empty i = 0, bits 000 1 i = 1, bits 001 1 2 i = 2, bits 011 2 i = 3, bits 010 2 3 i = 4, bits 110 1 2 3 i = 5, bits 111 1 3 i = 6, bits 101 3 i = 7, bits 100

Notice what the rule produces: consecutive lines differ by exactly one item joining or leaving. That is a THEOREM about the rule, not part of the specification, and the difference matters. "Print them so that consecutive subsets differ in one item" does not pin the order, because many such sequences exist. The formula above pins exactly one.

## Why the order has to be pinned, and pinned without naming a program

A set of answers has no order. If a statement says only "print them all", two correct programs produce two different outputs and no automated check can tell a correct program from a broken one. So the order is part of the specification.

The second trap is pinning it as "the order your search finds them in". That names a program rather than a rule, and it is not a specification: a search that tries its options in a different sequence finds the same answers in a different order and is equally entitled to call itself correct. The rule below mentions no search.

## What most people try first

Print the subsets in the order of the plain binary counter, i from 0 to 2^n - 1, reading i itself as the membership bits. That is the order #1146 uses and it is a different order: going from i = 3 to i = 4 changes three bits at once. Someone who has met "all subsets" before will produce that order by habit, and every line after the second will be in the wrong place.

The other instinct is to generate the subsets some other way and then sort them into the required order. That needs the required order as a comparison, which means computing, for each subset, which line number it belongs on, which means inverting the formula. It is possible and it is more work than generating directly.

## Generating directly

The formula is the program:

for i in 0 .. 2^n - 1: g = i XOR (i >> 1) print the items whose bit is set in g

i >> 1 is i with its bits shifted one place down, and XOR sets a bit when exactly one of its inputs has it. So bit j of g is bit j of i differing from bit j+1 of i. There is no search here at all, which is the point: the order was the hard part and once it is named precisely the generation is a loop.

## Why consecutive lines differ in one item

Going from i to i + 1 in binary flips a trailing run of 1s to 0s and the 0 above them to 1. Write i = p 0 1^k for some prefix p, so i + 1 = p 1 0^k. Then g(i) = p' 1 0^(k-1) 1 and g(i+1) = p' 1 0^k where p' is the part contributed by the prefix, which is the same for both because the prefix bits and their neighbours are unchanged above the flip. The two differ in exactly the one bit at position k. So exactly one item joins or leaves.

## Overflow

2^n with n at most 10 is 1024, and the shift is by one place, so nothing approaches INT_MAX = 2147483647. In JavaScript the bitwise operators truncate to 32 bits, which is harmless at 10 bits and worth saying rather than assuming.

## Cost

O(2^n * n), which is the size of the output, so it is optimal.

Constraints - `1 ≤ n ≤ 10`