Solved with GrantStar, OronSH, and pikapika007. The answer is $\boxed{k + 4}$. Construction is \[\begin{cases} \{-(t+2), -(t+1), \ldots, -1, 1, 2, \ldots, t+2 \}& \text{if } k = 2t \\ \{-(t+2), -(t+1), \ldots, -1,0,1,2,\ldots, t + 2\} & \text{if } k = 2t + 1 \\ \end{cases}\]for each positive integer $t$ (this gives a construction for all positive integers $k\ge 2$). We can check these sets have $k + 4$ elements. Claim: In this construction, each number can be written as the sum of two other distinct elements of the set. Proof: For any number $m$ not equal to $-(t+2), 1, $ or $2$, add up $(m-1) + 1$ (since $m-1\ne 1$ and they are both in the set) and for $m\in \{-(t+2), 1, 2\}$, add up $(m+1) + (-1)$ (this is possible since $m+1\ne -1$ and they are both in the set). $\square$ We can split the construction for $2t$ into $t+2$ pairs $(-(t+2), t+2), (-(t+1), t+1), \ldots, (-1, 1)$. To show each number can be written as the sum of $2t$ other elements, we can just find two elements adding up to it, and then add the $t-1$ remaining pairs (ones that don't include that number or the ones adding up to it). In the construction for $2t + 1$, if we want to make any nonzero number as the sum of $2t+1$ elements, we can use the construction for $2t$, and just add zero to that. If we want to make $0$, then we can use \[ 0 = (-1) + (-2) + 3 + (4 + (-4)) + (5 + (-5) ) + \cdots + ((t+2) + -(t+2))\] Therefore $n = k + 4 $ works for any positive integer $k\ge 2$. It remains to show $n\ge k + 4$. Suppose we had a working $n < k + 4$. Call the numbers $a_1>a_2>\cdots > a_n$. Notice $a_1$ is positive, otherwise it cannot be the sum of other elements. If $n = k + 1$, then we get that each number is the sum of the rest of the elements, so \[\sum_{i=1}^n a_i = \sum_{k=1}^n \sum_{1\le i\le n, i\le k}^n a_i = (n-1)\sum_{i=1}^n a_i\]therefore $\sum_{i=1}^n a_i = 0$. But now we know $a_1 = (a_2 + \cdots + a_n) $ and also $a_1 = -(a_2 + \cdots + a_n)$, so $a_1 = 0$, absurd since $a_1>0$. We notice that $a_1$ is the sum of $k$ numbers so it must be at most $M = a_2 + \cdots + a_{k + 1}$. We also notice that $a_n$ is the sum of $k$ numbers so it must be at least $N = a_{n-k} + a_{n - k + 1} + \cdots + a_{n-1}$. If $n = k + 2$, then $M = N$, so $a_1 \le M = N \le a_n$, contradiction because $a_1>a_n$. If $n = k + 3$, then \[0<a_1 - a_2 \le M - a_2 = N - a_{n-1} \le a_n - a_{n-1}<0,\]absurd. Therefore the smallest working value of $n$ is $k + 4$.

The answer is $k+4$. The construction is the integers from $-\left\lfloor \frac k2 \right\rfloor -2$ to $\left\lfloor \frac k2 \right\rfloor +2$ inclusive, except we remove $0$ for even $k$. I honestly don't care enough to prove this works just do stuff. Let $a_1 < a_2 < \dots < a_n$. The bound is obtained by noting that \begin{align*} a_1 &\geq a_2 + a_3 + \dots + a_{k+1}\\ a_n &\leq a_{n-k} + a_{n-k+1} + \dots + a_{n-1} \end{align*}Then \[ a_3 + \dots + a_{k+1} < 0 < a_{n-k} + a_{n-k+1} + \dots + a_{n-1}, \]and then $n-k >3$ or $n\geq k+4$.

We claim the answer $n=k+4.$ The example is a set of all integers from segment between $-\lfloor k/2\rfloor -2$ and $\lfloor k/2\rfloor +2,$ except for the $0$ if $k$ is even. By a routine induction it works. In order to prove the bound for the set of reals $a_1<a_2<\ldots <a_n$ $(n\geq 3)$ consider the following inequalities: $$a_1\geq \sum_{i=2}^{k+1} a_i>a_1+\sum_{i=3}^{k+1} a_i, \quad \quad a_n\leq \sum_{i=1}^{k} a_{n-i}<a_n+\sum_{i=2}^{k} a_{n-i}=a_n+\sum_{i=n-k}^{n-2} a_i$$It follows that $\sum_{i=3}^{k+1} a_i<0<\sum_{i=n-k}^{n-2} a_i,$ therefore $n-k>3\implies n\geq k+4$ as desired.

this is not algebra. Upper Bound. Take the following construction for $n=k+4.$: \[\begin{cases} k=2m, &\{m+2, m+1, \dots, 1, -1, \dots, -(m+1), -(m+2)\} \\ k=2m+1, &\{m+2, m+1, \dots, 1, 0, -1, \dots, -(m+1), -(m+2)\} \end{cases}\] First we show that every element in our construction of $k=2m$ can be expressed as the sum of two other numbers in the set. Observe that for any $r \neq m+2, -1,$ picking elements $r+1$ and $-1$ suffice. Note $m+2=(m+1)+1$ and $-1=-2+1.$ Now pair up the elements into $\{m+2, -(m+2)\}, $ $\dots,$ $\{1, -1\}.$ Expressing any number as the sum of two other numbers in the set disturbs at most two of these pairs, so after we do so, for the remaining $2(m-1)$ numbers, pick $m-1$ of the remaining untouched pairs and include them into the total sum. Since each pair contributes $0$ to the total sum, it follows that each element in this construction can be expressed as the sum of $k$ other elements in the set. For the $k=2m+1,$ the logic carries over from before that each nonzero element can be expressed as the sum of $2m$ other elements in the set. For each of these, simply include $0$ into the set to make it $2m+1.$ Observe $0$ can also be expressed as the sum of $2m+1$ elements, since $(m+1)+1-(m+2)=0,$ and after this there still remain $2(m-1)$ elements, of which we just pick all remaining untouched pairs (there must exist $m-1$ of these, since we only disturbed three of them and there are $m+2$ to begin with) and add them to the sum. Lower Bound. It remains to check $n \le k+3$ fail. Without loss of generality, let $a_1 < a_2 < \dots < a_n.$ Then $\min\{a_1\}=a_2+ \cdots + a_{k+1}$ and $\max\{a_n\}=a_{n-k}+ \cdots + a_{n-1}.$ Since $a_n$ is the largest element in the set, it must be positive. But now \[a_3+ \cdots + a_{k+1} < 0 < a_{n-k}+ \cdots + a_{n-2}.\]This forces $n-k>3 \implies n>k+3.$

Let $a_1<a_2<\dots<a_n$ be members of the set with described properties. Note that \begin{align*} a_1 &\ge a_2+a_3+\dots+a_{k+1}\\ a_n &\le a_{n-k}+a_{n-k+1}+\dots+a_{n-1} \end{align*}The first gives \[a_3+\dots+a_{k+1}<0\]While the second gives \[a_{n-k}+\dots+a_{n-1}>0\]so $n-k>3$ which implies $n\ge k+4$ which is the answer. The construction is omitted.

Answer is $n = k+4$. Suppose $n = k+3$, then let the numbers be $a_1 < a_2 < \cdots < a_n$. $$a_n \leq a_{3}+a_4 + \cdots + a_{n-1}$$ $$a_1 \geq a_{2}+a_3+ \cdots + a_{n-2}$$ So $a_n - a_1 \leq a_{n-1}-a_2$, contradiction. $n < k+3$ is trivial. Construction: $\{-s, -s+1, \ldots, -2, -1, 1, 2, \ldots, s-1, s\}$ for even $n$, $\{-s, -s+1, \ldots, -2, -1, 0, 1, 2, \ldots, s-1, s\}$. Verification is exercise.

The answer is $n = k+4$. Construction: For $k = 2n$, with $n$ being an integer, take \[ A = \{ -n-2,-n-1,\ldots,-1,1,2,\ldots,n+2 \} . \]For $k+1=2n+1$, take $A \cup \{0\}$. We now show this works. Consider $k$ even; there are three cases. Let the target number be $a$. Case 1: $a=1$ or $a=2$. To get $1$ pick the numbers $-n-2,\ldots,-4,-1,2,4,\ldots,n+2 $. To get $2$, replace $'2'$ with $'3'$. Case 2: $a \geq 3$. Take the numbers \[-n-2,-n-1,\ldots,-a-1,-a+1,\ldots,-3,1,2,4,5,6\ldots,n+2.\] Case 3: $a < 0$. Simply flip the signs in the previous cases. For $k$ odd ($k=2n+1$), include $0$ if the target is nonzero, otherwise use \[ -n-2,-n-1,\ldots,-3, 1,2,4,5,\ldots,n+2 \]to obtain $0$. We now show $n < k+4$ fails. Clearly, $n > k$. If $n = k+1$, let the numbers be $a_1 < a_2 < \ldots < a_{k+1}$. Then \[a_{k+1} = a_1 + a_2 + \ldots + a_k < a_1 + a_2 + \ldots + a_{k-1} + a_{k+1} = a_k,\]a contradiction. If $n = k+2$, let the numbers be $a_1 < \ldots < a_{k+2}$ and $\sum_{i \in [k+2]} a_{i} = S$. This forces $2a_1 = S - a_{k+2}$ and $2a_{k+2} = S - a_1$, contradiction. If $n = k+3$, then \[ a_{k+3} \leq a_3 + a_4 + \ldots + a_{k+2} \text{ and } a_1 \geq a_2 + a_3 + \ldots + a_{k+1}. \]Hence, $a_{k+3} - a_1 \leq a_{k+2} - a_2$, a contradiction.

okay that took longer than it should have The answer is $n=k+4$. For $k=2a$ take \[-(a+2),\dots,-1,1,\dots,a+2\]and for $k=2a+1$ take \[-(a+2),\dots,-1,0,1,\dots,a+2.\]To show the constructions work, note the following: The sum $s$ of all values is $0$. For any value $a_i$ we just need to find $a_x,a_y,a_z$ where $2a_i+a_x+a_y+a_z=0$. The $k=2a+1$ case is nearly identical to the $k=2a$ case; we can construct any nonzero number in the $k=2a+1$ case if we can do so in the $k=2a$ case, because then we can add $0$ to the addends. We can also generate $0$ by taking $a_x+a_y+a_z=0$ in the above. The $k=2a$ can be proven inductively: we can construct any number in the $k=2a+2$ case if we can do so in the $k=2a$ case by adding $a+3$ and $-(a+3)$ to the addends. Furthermore we can construct $a+3$ by taking $a_x=-(a+3)$ and $a_y+a_z=-(a+3)$. By symmetry we can also construct $-(a+3)$. Now we show that $n\in \{k+1,k+2,k+3\}$ fail. Denote the sum by $s$ and let values be $a_1,\dots,a_n$. For every $a_i$ there exists a set $S$ of values in sequence $a$ where $|S|=n-(k+1)$ and \[2a_i+f(S)=s\]where $f$ sums the elements. The idea is that we can define \[b_i=a_i-\frac{s}{|S|+2}\]and at this point we can actually define $S'$ as the transformed set, then \[2b_i+f(S')=0\]and since $|S|=|S'|\le 2$ it follows that taking $b_i$ with maximal magnitude is a contradiction. Done.

We claim the answer is $n=k+4$, with constuction $$\begin{cases} \{-\frac{k}{2}-2, -\frac{k}{2}-1, \dots, -1, 1, 2, \dots \frac{k}{2}+2 \} & k \equiv 0 \pmod{2} \\ \{ -\frac{k+3}{2},\dots ,-1,0, 1, 2, \dots \frac{k+3}{2} \} & k \equiv 1 \pmod{2} \end{cases}$$Note that if the set was all nonnegative numbers or nonpositive numbers then one the minimal/maximal wouldn't have numbers in the set to sum to it. Now FTSOC suppose a set with size $k+1$ satisfies this, let it's elements be $a_1 < a_2 < \dots < a_{k+1}$ Then we require $$a_1 > a_1 + a_2 +\dots+ a_{k+1}$$$$a_{k+1} < a_1 + a_2 +\dots+ a_{k+1}$$Contradiction. Now FTSOC suppose a set with size $k+2$ satisfies this, let it's elements be $a_1 < a_2 < \dots < a_{k+2}$, and let $\sum a_i =S$ Then we require for some $j, p$ $$a_1= S-a_j-a_1$$$$a_{k+2}= S- a_p - a_n$$$$2(a_{k+2}-a_1)= a_j - a_p$$But $a_{k+2}-a_1$ is greater than all possible other differences contradiction. Now FTSOC suppose a set with size $k+3$ satisfies this, let it's elements be $a_1 < a_2 < \dots < a_{k+3}$, and let $\sum a_i =S$ Then we require for some $j, p, l, m$ $$a_1= S-a_j-a_p-a_1$$$$a_{k+3}= S- a_p-a_l - a_n$$$$2(a_{k+3}-a_1)= a_p+a_l - a_j-a_m$$But $a_{k+3}-a_1$ is greater than all possible other differences contradiction.

A proof of the lower bound: Suppose otherwise, that $n-k\leq 3$ Order the numbers in increasing order $a_1, a_2, \dots a_n$. It is not hard to show that both a positive and negative term exist by considering the maximal and minimal terms and how they can be written as sums of other terms respectively; in fact, we know that there exist at least 2 positive and 2 negative terms from this same fact. Hence denote $S = a_3 + a_4 + \dots + a_{n-2}$, and let there be $a$ positive and $b$ non-positive terms. Now the maximal possible sum is at least $a_n$, i.e. $a_n \leq a_{n-1}+a_{n-2} \dots a_{n-k}$, From $a_n>a_{n-1}$ we obtain $a_{n-2} + \dots + a_3 \geq a_{n-2} + \dots + a_{n-k} > 0$, where the first inequality holds from $a_2, a_1 < 0$ and $n-k \leq 3$. Hence $S>0$ On the other hand applying this same argument when we multiply all terms by $-1$ yields $S<0$, a contradiction.

Feels like a very shallow problem: obviously $n \approx k$ and for $n$ too small little local things mess up. Let the elements be $m = a_1<a_2<\cdots<a_n = M$. The answer is $n = k+4$. If $n = k+1$, then $a_i = S-a_i$ for each $i$, hence $S = 2a_i$ and all the $a_i$ are equal, contradiction. If $n = k+2$, then $a_i = S - a_i - a_{f(i)}$ for some $f(i)$, so \[2M+m \leq S = 2a_n + a_{f(n)} = 2a_1 + a_{f(1)} \leq 2m + M\]which is a contradiction. If $n = k+3$, then $a_i = S - a_i - a_{f(i)} - a_{g(i)}$ for some $f(i)$ and $g(i)$. Once again, \[2M + 2m < 2a_n+a_{f(n)} + a_{g(n)} = 2a_1 + a_{f(1)} + a_{g(1)} < 2M+2m\]which is a contradiction again. When $n = k+4$, take $-(m+2), -(m+1), \dots, -1, 1, 2, 3, \cdots, m+2$ when $k = 2m$. Add another zero when $k = 2m+1$.

The smallest such $n$ is $\boxed{k+4}$. For the rest of the solution assume that $x_1<x_2<\dots<x_n$ and let $S=x_1+x_2+\dots+x_n$. Construction: If $n=2a$ consider $\{-k,-k+1,\dots,-1,1,\dots,k-1,k\}$ and for $n=2a+1$ consider $\{-k,-k+1,\dots,-1,0,1,\dots,k-1,k\}$. We will provide an explanation for the first case with the other being nearly identical. The idea is if you want to sum to some element $b$ you add either $b+1$ and $-1$ to the sum or $b-1$ and $1$ to the sum. Then add the remaining $\pm$ pairs creating a subset with sum $b$ and $2a-4$ elements. Bound: If $n=k+1$ then $x_i=S-x_i$, a contradiction. If $n=k+2$ then there must exist a $j\neq i$ for each $i$ such that $x_i=S-x_i-x_j$. Clearly $i\mapsto j$ is a bijection. Then summing over all such equations we get $S=0$ so by a size argument either $x_1$ or $x_n$ yields a contradiction. Now assume $n=k+3$. It is not hard to show that $$S-x_1-x_2\leq 2 x_n$$$$S-x_1-x_2\leq 2 x_{n-1}$$$$2x_1\leq S-x_{n-1}-x_{n}$$$$2x_2\leq S-x_{n-1}-x_{n}$$Summing these we get that all the inequalities must be equalities, a contradiction.

OP casework!!! Answer: $\boxed{n=k+4}$ Take $a_1<a_2<\cdots<a_n$. From the problem we have $a_1\geq a_2+\cdots a_{k+1}$ and $a_n\leq a_{n-k}+\cdots +a_{n-1}$. According to the problem $n\geq k+1$ so we have the following cases: Case I: $n=k+1$ From the above conditions we have a contradiction because we get $a_1>a_{k+1}$. Case II: $n=k+2$ Like in Case I we get $a_1>a_{k+2}$ which is a contradiction. Case III: $n=k+3$ We have $a_1\geq a_2+\cdots a_{k+1}$ and $a_3+\cdots a_{k+2}\geq a_{k+3}$ Case IV: $n=k+4$ Subcase I: $k$ is even. If $k=2m$ then take the set of $\{-r,r\}$ where $0\leq r\leq m+2$ (Motivation: If any $r$ can be expressed as the desired form then so can $-r$ be represented in that form and $m+2$ because we are looking at $n=2m+4$.) Now for different value for $m$ we take as $r$. $r=1$ : To get $1$ pick the numbers $-m-2,\cdots,-4,-1,2,4,\cdots,m+2 $. $r\geq3$ : Take $-m-2,\cdots,-r-1,-r+1,\cdots,-3,1,2,4,\cdots,m+2.$ $r < 0$ : Change the signs in the previous cases. Subcase II: $k$ is odd. For $k=2m+1$, similar construction works just add $0$ as well. Construct $-m-2,-m-1,\cdots,-3, 1,2,4,\cdots,m+2 $ to obtain $0$.

Remove the word "other" from the problem, then try. It shall be fun