Suppose I have a sequence, where for each element I can choose one out of two numbers. I would like to find a compact formula to write all the possible sums of all the possible sequences.
For example, suppose I have $\langle(1,2), (3,4) \rangle$
The possible sequences are $\langle 1, 3 \rangle$, $\langle 1, 4 \rangle$, $\langle 2, 3\rangle$, $\langle 2, 4\rangle$ and therefore all the possible sums are $4, 5, 5, 6$ respectively.
It seems that the following holds. Assume that the compact formula is so good that it is effectively computable (which, in general, probably, is not true, for instance, for a formula $\tan 2^{2^n}$ (?)). Next, to be independent on a definition of a computation algorithm, we assume the Church-Turing thesis. Then your question has a negative answer (even if we consider only non-negative integers) because it asks about an NP-complete problem. Indeed, from one side, the sum listing problem is in NP, because it can be solved by $2^n$ independent automata in linear time. From the other side, given a set $A=\{a_1,\dots, a_n\}$ of natural numbers and a natural number $b$, to decide whether there exists a subset of $A$ whose sum is $b$ is a well-known decision problem; the subset sum problem, which is NP-hard. So if we consider the pairs $\langle (a_1,0),\dots, (a_n,0)\rangle$, the problem to decide whether $b$ is the sum of a possible sequence is NP-hard, too. Conversely, to decide whether $b$ is the sum of a possible sequence of the pairs $\langle (a_1,b_1),\dots, (a_n,b_n)\rangle$, it suffices to decide whether $b-(a_1+\cdots+a_n)$ is the sum of a possible sequence of a submultiset of a multiset $\{b_1-a_1,\dots, b_n-a_n\}$.
Acknowledgement. Author thanks to Prof. Dr. Alexander Wolff for his valuable remarks and corrections.