1235. Every Subset, Smallest Ones First

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

> A subset with fewer members comes before a subset with more. Among subsets of > the same size, the one whose member list is smaller comes first, comparing the > lists position by position with the members written in increasing order.

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

n = 3 empty 1 2 3 1 2 1 3 2 3 1 2 3

## 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

Generate the subsets and sort them with the two keys. That is correct and it needs all 2^n subsets in memory. It also invites the key to be written as a single string, which is wrong: the size has to be compared as a NUMBER. Sorting the printed lines as text puts 1 2 before 3 because 1 sorts before 3, and at n = 10 it also puts 10 before 2.

The second instinct is the plain binary counter from #1146, which produces a third order entirely: 1, 2, 1 2, 3, 1 3, and so on, mixing the sizes.

## Generating directly

The order is a size loop around a lexicographic loop, so write it as one:

for size in 0 .. n: for each subset of that size, in increasing order of its member list: print it

and the inner loop is the standard combination step: hold the members in increasing order, starting at 1, 2, ..., size, and to advance, find the LAST member that is not yet at its maximum and raise it, then reset every member after it to one more than its predecessor. The maximum for the member at position j out of size is n - (size - 1 - j), because the members after it have to fit above it.

Note that this is the mirror image of the colex step in #1234, which raises the FIRST member that can rise. Raising the last gives lexicographic order within a size and raising the first gives colex order; the two generators differ by which end they scan from, and nothing else.

## Why that produces the required order

The outer loop produces the sizes in increasing order, which is the first key. Within a size, raising the last member that can rise and resetting the ones after it to their smallest legal values produces the next list in increasing order: the lists agree before the raised position, the new one is larger there, and the positions after it are as small as they can be, so nothing lies between them.

## The settled boundaries

The empty subset is printed first, as the word empty, which is a decision the statement has to make and does. n = 1 gives two lines.

## Cost

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

Constraints - `1 ≤ n ≤ 10`