Optimal addition subtraction chain An addition-subtraction chain, is a sequence \$a_1, a_2, a_3, ... ,a_n\$, such that \$a_1=1\$ and for all \$i &gt; 1\$, there exist \$j,k&lt;i\$ such that \$a_i = a_j \pm a_k\$.
Your task, is given a number \$x\$, find the shortest addition-subtraction chain, such that \$a_n = x\$.
Rules

You can assume the input is a valid integer
In case there are multiple optimal addition-subtraction chains, you can print any non-empty subset of them
You may use any reasonable I/O method (you can output it reversed, with any separator you want, in any base you want, ect.)

Test cases
(these are one solution, you can output anything valid with the same length)
these are all the numbers with a addition subtraction chain of length 6 or less
-31 -&gt; [1, 2, 4, 8, 16, -15, -31]
-30 -&gt; [1, 2, 4, 8, 16, -15, -30]
-28 -&gt; [1, 2, 4, 8, -6, -14, -28]
-24 -&gt; [1, 2, 4, -2, -6, -12, -24]
-23 -&gt; [1, 2, 4, 8, 12, 24, -23]
-22 -&gt; [1, 2, 4, 6, -5, -11, -22]
-21 -&gt; [1, 2, 3, 6, 12, -9, -21]
-20 -&gt; [1, 2, 4, 6, -5, -10, -20]
-19 -&gt; [1, 2, 4, 8, -3, -11, -19]
-18 -&gt; [1, 2, 4, -1, 8, -9, -18]
-17 -&gt; [1, 2, 4, -3, 7, -10, -17]
-16 -&gt; [1, 2, 3, -1, -4, -8, -16]
-15 -&gt; [1, 2, 4, 8, 16, -15]
-14 -&gt; [1, 2, 4, 8, -7, -14]
-13 -&gt; [1, 2, 4, 6, -3, -7, -13]
-12 -&gt; [1, 2, 4, -3, -6, -12]
-11 -&gt; [1, 2, 4, 6, -5, -11]
-10 -&gt; [1, 2, 4, -2, -6, -10]
-9 -&gt; [1, 2, 4, 8, -1, -9]
-8 -&gt; [1, 2, 4, 8, 0, -8]
-7 -&gt; [1, 2, 4, -3, -7]
-6 -&gt; [1, 2, 4, 8, -6]
-5 -&gt; [1, 2, 4, -3, -5]
-4 -&gt; [1, 2, 4, 8, -4]
-3 -&gt; [1, 2, -1, -3]
-2 -&gt; [1, 2, 4, -2]
-1 -&gt; [1, 0, -1]
0 -&gt; [1, 0]
1 -&gt; [1]
2 -&gt; [1, 2]
3 -&gt; [1, 2, 3]
4 -&gt; [1, 2, 4]
5 -&gt; [1, 2, 4, 5]
6 -&gt; [1, 2, 4, 6]
7 -&gt; [1, 2, 4, -3, 7]
8 -&gt; [1, 2, 4, 8]
9 -&gt; [1, 2, 3, 6, 9]
10 -&gt; [1, 2, 4, 5, 10]
11 -&gt; [1, 2, 4, 6, 5, 11]
12 -&gt; [1, 2, 4, 6, 12]
13 -&gt; [1, 2, 3, 5, 10, 13]
14 -&gt; [1, 2, 4, 6, 10, 14]
15 -&gt; [1, 2, 3, 6, 9, 15]
16 -&gt; [1, 2, 4, 8, 16]
17 -&gt; [1, 2, 4, 8, 9, 17]
18 -&gt; [1, 2, 4, 8, 9, 18]
19 -&gt; [1, 2, 4, 8, 9, 17, 19]
20 -&gt; [1, 2, 4, 5, 10, 20]
21 -&gt; [1, 2, 4, 8, 16, 5, 21]
22 -&gt; [1, 2, 4, 8, 12, 24, 22]
23 -&gt; [1, 2, 4, 8, 16, -15, 23]
24 -&gt; [1, 2, 3, 6, 12, 24]
25 -&gt; [1, 2, 4, 8, 12, 13, 25]
26 -&gt; [1, 2, 4, 6, 10, 16, 26]
27 -&gt; [1, 2, 4, 5, 9, 18, 27]
28 -&gt; [1, 2, 4, 8, 12, 14, 28]
30 -&gt; [1, 2, 4, 5, 10, 20, 30]
31 -&gt; [1, 2, 4, 8, 16, -15, 31]
32 -&gt; [1, 2, 4, 8, 16, 32]
33 -&gt; [1, 2, 4, 8, 16, 32, 33]
34 -&gt; [1, 2, 4, 8, 16, 17, 34]
36 -&gt; [1, 2, 3, 6, 9, 18, 36]
40 -&gt; [1, 2, 4, 8, 12, 20, 40]
48 -&gt; [1, 2, 4, 8, 12, 24, 48]
64 -&gt; [1, 2, 4, 8, 16, 32, 64]

you can find a list of all optimal addition subtraction chains for each of them here
This is code golf, so the shortest answer in bytes in each language wins.
Brachylog, 19 17 bytes
∧≜;1⟨∋{+|-}∋⟩ᵃ⁽?t

Try it online!
I guess I shouldn't be too surprised, but funnily enough this produces the exact same outputs as xash's solution--up to \$n = 13\$ after which both time out. Takes input through the output variable and outputs through the input variable.
   1                 Starting with 1,
             ᵃ       repeat on the list of previous results
∧≜;           ⁽      as few times as necessary:
       +             add
      { |-}          or subtract
    ⟨∋     ∋⟩        one element and another (not necessarily distinct),
               ?     such that the final list of results is the input variable
                t    and its last element is the output variable.