1158. Selections Ordered by Their Total

Given n distinct integers, print every selection, ordered by its TOTAL from smallest to largest. Selections with equal totals are ordered the usual way for this block: position by position numerically, shorter prefix first.

3 -2 -1 3 -> -2 -1 total -3 -2 total -2 -1 total -1 empty total 0 -2 -1 3 total 0 -2 3 total 1 -1 3 total 2 3 total 3

Look at the fourth and fifth lines. Both total 0, so the tie-break decides, and empty is shorter than everything, so it comes first. That is the whole reason this problem exists: the empty selection stops being the first line and lands wherever its total of 0 puts it.

## What most people try first

Generate the selections in the usual order and hope the totals come out increasing. They do not, and with negative values present they are not even close: -2 -1 has the smallest total and the usual order puts empty first.

A second instinct is to sort the values by size and expect that to fix the order. It cannot. The total of a selection does not determine its position among selections that differ in length, and no generation order over values can produce an ordering that depends on a sum computed later.

## The method

Enumerate every selection, remember each one WITH its total, then sort by the pair (total, the selection itself).

go(i): record a COPY of cur, with sum(cur) for j in i .. n-1: cur.push(a[j]); go(j + 1); cur.pop() sort by (total, selection)

Two details are load bearing. The recorded value must be a COPY: storing the live list leaves every record pointing at the same object, which after the last undo is empty, so the output is the right number of blank lines. And the tie-break must be the sequence comparison, not the text, because -10 sorts before -2 numerically and after it as text.

## Why it is correct

The enumeration is the one from problem 1146 and produces each selection exactly once, so the multiset of lines is right whatever order they end up in. The order is then whatever the comparison says, and the comparison is a total order on (total, sequence) because no two distinct selections of distinct values are the same sequence. So the output is uniquely determined, which is what makes the problem answerable at all.

## The output convention, shared by every problem in this block

Values inside one selection are separated by single spaces and printed in increasing order. Selections are printed one per line. Two selections are ordered by comparing them position by position NUMERICALLY, and when one is a prefix of the other the shorter one comes first, so the empty selection is always first. The empty selection prints as the word empty. If there are no selections at all, print none.

The empty selection always exists, so none is never printed. Its total is 0.

## Overflow

With n at 14 and values within a thousand, a total stays inside 14000, so nothing overflows. The running total is small on purpose, because the point of this problem is the ordering rather than the arithmetic.

## Cost

2^n selections, each costing O(n) to build and compare, and the sort adds a log factor: O(2^n * n^2) as a loose bound, 16384 lines at n = 14.

Constraints - `1 ≤ n ≤ 14` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.