# Enumerate all valid orders of subset sums

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

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.