Proof that a sum $x$ is found in$ [1, n (n + 1) / 2]$ squence In the subset sum existance problem, we have a sequence of integers. We are given an integer $x$ that we should look for a possible subsequence that sum to $x$. For example, if we have the sequence $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ and $x = 39$ then we have a subsequence $\{ 10, 9, 8, 7, 5 \}$ that sums up to $39$.
I want to prove that any sequence $[1, n]$ have a subsequence sum for any $x \in [1, n(n + 1) / 2]$. In the previous example, $n = 10$ so that any $x$ between $1$ and $55$ inclusive can be found. I have made a program and tested that this is true. Now I want to determine a proof.

Here is an alternative approach: consider the case for $n = 5$.
Then $n(n+1)/2 = 5(6)/2 = 15$.
Observe that we can write the numbers $1, \ldots, 15$ as follows:
$1, 2, 3, 4, 5,$
$1+5, 2+5, 3+5, 4+5,$
$1+4+5, 2+4+5, 3+4+5,$
$1+3+4+5, 2+3+4+5,$
$1+2+3+4+5$.
The number of elements summed for entries in the above rows, respectively, are: $1, 2, 3, 4, 5$.
By construction, they are distinct and increasing by one, beginning with $1$ and ending with $15$.
The above can be similarly written out for the general $n$ instead of $15$.
