Given an positive integer $ n$ , we define an *order of subset sums* to be a sequence of *all* subsets of $ \{1,\ldots,n\}$ . For example, when $ n=2$ , the sequence $ \emptyset,\{1\},\{2\},\{1,2\}$ is an order of subset sums.

We call an order of subset sums $ S_1,\ldots,S_{2^n}$ valid if there exist real numbers $ 0<x_1<\cdots<x_n$ such that $ \sum_{i\in S_1}x_i<\cdots<\sum_{i\in S_{2^n}}x_i$ . For example, when $ n=2$ , the sequence $ \emptyset,\{1\},\{2\},\{1,2\}$ is a valid order of subset sums, but the sequence $ \emptyset,\{1\},\{1,2\},\{1\}$ is not a valid order of subset sums because we cannot make $ x_1+x_2<x_1$ .

The question is, given $ n$ , how to enumerate all possible valid orders of subset sums. I know this problem cannot be solved in time polynomial in $ n$ , because there may be exponentially many valid orders of subset sums, so an algorithm with exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders of subset sums, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order of subset sums is valid.