Number of orderings of subset sums In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may assume all $2^n$ subset sums are distinct.
Example: Suppose $n=2$. There are four subset sums: $0$, $a_1$, $a_2$, and $a_1+a_2$. There are eight possible orderings:
\begin{eqnarray}
0 &<& a_1 < a_2 < a_1 + a_2\\
0 &<& a_2 < a_1 < a_1 + a_2\\
a_1 &<& 0 < a_1 + a_2 < a_2 \\
a_2 &<& 0 < a_1 + a_2 < a_1 \\
a_1 &<& a_1 + a_2 < 0 < a_2 \\
a_2 &<& a_1 + a_2 < 0 < a_1 \\
a_1 + a_2 &<& a_2 < a_1 < 0 \\
a_1 + a_2 &<& a_1 < a_2 < 0.
\end{eqnarray}
All other orderings of these four expressions, such as
$$
a_1 + a_2 < 0 < a_1 < a_2
$$
are not possible.
Motivation: This problem is directly related to the well-known NP-complete "subset sum" problem in computer science. I am wondering whether the pure combinatorics of that problem render it especially difficult.
My guess is that the problem I pose here has been asked before: I think it's a pretty straightforward way to understand something about the difficulty of the subset sum problem.
 A: Here is a recursive approach.
Let $n$ be the order of a set. So it has $2^n$ subsets. Define $f(n)$ as the number of possible orderings if the input is the order $n$ of a set.
I claim that $f(n+1)=f(n).[(2^n)(2^n-1)+2]$
Now, to give a weak proof, I would explain it this way: Let's assume we know all possible orderings for sets of order $n=k$. Let's focus on one of the possible orderings. Then, we mark the numbers, corresponding to each sum, on a axis of real number with spikes. To make an ordering of a set of order $n=k+1$, we add an arbitrary number to the marked numbers. So, actually we are shifting the numbers that we had. To imagine it more conveniently, we can make a duplicate of the axis (with the same spikes) that we had for $n=k$ and put it below the original one. Adding a new number to a set is equivalent to shift the duplicate axis with the amount of the new member.
The next step is to see how the new possibilities for $n=k+1$ is created. As we need to consider all possibilities, we may take a new member $x$ which is variable. $x$ starts from $0$ and goes to infinity and $x$ actually shifts the lower axis. Every time two spikes from the lower and the upper axes passes each other, we have a new ordering. The first spike, from the lower axis, would pass $2^k-1$ spikes, from the upper axis. The second spike would pass $2^k-2$ spikes and so on. Hence, we have a total of $(\sum_{i=1}^\mathbb{2^k-1} i)+1=(2^k-1)+(2^k-2)+...+1+1$ (the one at the end is an adjustment) possibilities for a positive $x$. If negative $x$ cases are counted, the final result would be $(2^k)(2^k-1)+2$. Note that this is for one ordering of order $n=k$. So we multiply it by the number of possible orderings of $n=k$ which is $f(k)$.
