1146. Every Subset
Given n distinct integers, print every subset, one per line.
Sort the values first, print each subset's values in increasing order, and print
the subsets themselves in lexicographic order. The empty subset is a subset and
prints as the word empty.
Problem #219 counts how many subsets there are, which is 2^n and needs no
search. This asks for the subsets themselves, which is a different job: there is
nothing to memoise, because every answer is a distinct object rather than a
number that can be reused.
The shape is choose, recurse, undo. At each value there are two branches: leave it out, or take it. Take it by appending, recurse, then REMOVE it again before trying the other branch, or the next branch inherits a choice it never made.
Constraints - `1 ≤ n ≤ 16` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.
Input
The first line contains an integer n.
The second line contains n space-separated distinct integers.
Output
Print every subset on its own line, values separated by single spaces and in increasing order, the lines in lexicographic order. Print the empty subset as empty.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.