An addition-subtraction chain, is a sequence $$\a_1, a_2, a_3, ... ,a_n\$$, such that $$\a_1=1\$$ and for all $$\i > 1\$$, there exist $$\j,k 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 -> [1, 2, 4, 8, 16, -15, -31]
-30 -> [1, 2, 4, 8, 16, -15, -30]
-28 -> [1, 2, 4, 8, -6, -14, -28]
-24 -> [1, 2, 4, -2, -6, -12, -24]
-23 -> [1, 2, 4, 8, 12, 24, -23]
-22 -> [1, 2, 4, 6, -5, -11, -22]
-21 -> [1, 2, 3, 6, 12, -9, -21]
-20 -> [1, 2, 4, 6, -5, -10, -20]
-19 -> [1, 2, 4, 8, -3, -11, -19]
-18 -> [1, 2, 4, -1, 8, -9, -18]
-17 -> [1, 2, 4, -3, 7, -10, -17]
-16 -> [1, 2, 3, -1, -4, -8, -16]
-15 -> [1, 2, 4, 8, 16, -15]
-14 -> [1, 2, 4, 8, -7, -14]
-13 -> [1, 2, 4, 6, -3, -7, -13]
-12 -> [1, 2, 4, -3, -6, -12]
-11 -> [1, 2, 4, 6, -5, -11]
-10 -> [1, 2, 4, -2, -6, -10]
-9 -> [1, 2, 4, 8, -1, -9]
-8 -> [1, 2, 4, 8, 0, -8]
-7 -> [1, 2, 4, -3, -7]
-6 -> [1, 2, 4, 8, -6]
-5 -> [1, 2, 4, -3, -5]
-4 -> [1, 2, 4, 8, -4]
-3 -> [1, 2, -1, -3]
-2 -> [1, 2, 4, -2]
-1 -> [1, 0, -1]
0 -> [1, 0]
1 -> [1]
2 -> [1, 2]
3 -> [1, 2, 3]
4 -> [1, 2, 4]
5 -> [1, 2, 4, 5]
6 -> [1, 2, 4, 6]
7 -> [1, 2, 4, -3, 7]
8 -> [1, 2, 4, 8]
9 -> [1, 2, 3, 6, 9]
10 -> [1, 2, 4, 5, 10]
11 -> [1, 2, 4, 6, 5, 11]
12 -> [1, 2, 4, 6, 12]
13 -> [1, 2, 3, 5, 10, 13]
14 -> [1, 2, 4, 6, 10, 14]
15 -> [1, 2, 3, 6, 9, 15]
16 -> [1, 2, 4, 8, 16]
17 -> [1, 2, 4, 8, 9, 17]
18 -> [1, 2, 4, 8, 9, 18]
19 -> [1, 2, 4, 8, 9, 17, 19]
20 -> [1, 2, 4, 5, 10, 20]
21 -> [1, 2, 4, 8, 16, 5, 21]
22 -> [1, 2, 4, 8, 12, 24, 22]
23 -> [1, 2, 4, 8, 16, -15, 23]
24 -> [1, 2, 3, 6, 12, 24]
25 -> [1, 2, 4, 8, 12, 13, 25]
26 -> [1, 2, 4, 6, 10, 16, 26]
27 -> [1, 2, 4, 5, 9, 18, 27]
28 -> [1, 2, 4, 8, 12, 14, 28]
30 -> [1, 2, 4, 5, 10, 20, 30]
31 -> [1, 2, 4, 8, 16, -15, 31]
32 -> [1, 2, 4, 8, 16, 32]
33 -> [1, 2, 4, 8, 16, 32, 33]
34 -> [1, 2, 4, 8, 16, 17, 34]
36 -> [1, 2, 3, 6, 9, 18, 36]
40 -> [1, 2, 4, 8, 12, 20, 40]
48 -> [1, 2, 4, 8, 12, 24, 48]
64 -> [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.

• Commented May 15, 2021 at 17:51
• Do you actually need to use -15 to make 23, or could you just use 16-1 and then make 23 using 15+8?
– Neil
Commented May 15, 2021 at 17:55
• @Neil You could use 16-1 and then make 23. These are just a single solution my program found, other solutions with the same length exist for most of those. Commented May 15, 2021 at 17:56
• Can we output the addition-subtraction chain reversed? Commented May 15, 2021 at 21:17
• If we are interested in addition-subtraction chains only up to x=31, then it is sufficient to use just addition chains, which can make answers shorter. Commented May 17, 2021 at 12:49

# 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:
{ |-}          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.

• Oh, wow, this is so much cleaner! I had hoped describing the list beforehand would allow for some search optimizations and thus be faster then brute force – but that's probably too complicated. :-)
– xash
Commented May 15, 2021 at 19:04

# JavaScript (ES6), 104 bytes

A very basic and quite long implementation. But it does solve all test cases in ~20 seconds on TIO.

f=(n,l)=>(g=([...a],x)=>a.push(x)<l?a.some(x=>a.some(y=>g(a,x+y)||g(a,x-y))):r=x==n&&a)([],1)?r:f(n,-~l)


Try it online!

• Could you save a byte with a[l]-n and reversing that ternary? Commented May 15, 2021 at 19:35
• @Shaggy I've just saved a byte with a more convoluted update. I think a[l]-n (or a[l]^n, actually) would have failed for n=0. Commented May 15, 2021 at 19:37

# Python 3, 88 87 bytes

-1 byte thanks to dingledooper!

f=lambda n,x=[1],*a:x*(n in x)or f(n,*a,*[x+[a+c]for a in x for b in x for c in(b,-b)])


Try it online!

• Maybe you should import sys;sys.setrecursionlimit(10**6); to the header in TIO Commented May 15, 2021 at 18:09
• @CommandMaster I've added this now, but this doesn't help too much as the recursive solution is a lot slower than the already-slow iterative one anyways. (It takes ~50 times longer for 9)
– ovs
Commented May 15, 2021 at 20:53
• 87 bytes Commented May 15, 2021 at 21:13

head.(filtera).elem
a=[1]:do h<-a;i<-h;j<-h;[i-j:h,i+j:h]


Try it online!

a is the infinite list of all the addition-subtraction chains, sorted by length. The function head.(filtera).elem takes an integer (say n) and returns the first chain in a which contains n.

# Husk, 18 17 bytes

ḟ¡SṀ:S×+S+m_;;1€


Try it online!

-1 thanks to Leo

The longer I look at this, the less I have any idea why it seems to work. Probably something to do with the iterL overload that I didn't even know existed. I need coffee

• I've honestly never seen iterL actually get inferred in a program before. Nice answer. Commented May 16, 2021 at 5:21
• Very nice answer! One byte can be golfed by using Ṁ instead of om (Try it online!); I think this also makes it more understandable, but if you want I can provide an explanation of what's happening here :)
– Leo
Commented May 17, 2021 at 0:53
• @Leo Ah, I knew there had to be something--thanks! Commented May 17, 2021 at 5:58

# Jelly, 23 bytes

1+;_ɗþFQ;€Ʋ€Ẏ$Fċ³¬Ɗ¿ċƇ  Try it online! A full program taking a single argument and returning a list of all optimal addition subtraction chains, each in reverse order. ## Explanation 1 | Start with 1 Ɗ¿ | While the following is true: F | - Flatten list ċ³ | - Count the number of occurrences of the input ¬ | - Not (i.e. = 0)$          | Do the following:
Ʋ€            | - For each member of the list, do the following:
ɗþ                 |   - Do the following as a dyad mapping over the sublist for both left and right arguments
;                     |     - Concatenated to:
_                    |       - Subtract
F                |   - Flatten
Q               |   - Uniquify
;€             |   - Concatenate each value to the original sublist
Ẏ          | - Join lists together
ċƇ | Finally, keep only those list where the input appears


# Brachylog, 31 bytes

1g|g;Lc,1↔a₀ᵇb{kgj∋ᵐ{+|-}~t?}ᵐt


Try it online!

### How it works

? is the input of the current scope.

1g|g;Lc,1↔a₀ᵇb{kgj∋ᵐ{+|-}~t?}ᵐt
1g                              if ? is 1, return [1].
|                             else
g;L                          [[?], L]
c                         [?, L0, L1, …] (try shorter lists first)
,1↔                      [1, L0, L1, …, ?]
{             }ᵐ  map every
a₀ᵇb                  prefix except the first ([1]):
f.e. [1, L0, L1]
k                [1, L0]
gj              [[1, L0], [1, L0]]
∋ᵐ            select any element of each list, f.e.
[L0, 1]
{+|-}       try L0 + 1 and L0 - 1
~t?    is equal to L1
t return the last prefix (which is the list)


# Charcoal, 42 bytes

Ｎθ⊞υ⟦¹⟧ＦυＦ¬⊙υ№κθＦιＦ⁻⁺⁺ιλ⁻ιλι⊞υ⁺ι⟦μ⟧Ｉ⊟Φυ№ιθ


Try it online! Link is to verbose version of code. Very¹ slow, so only try it with single-digit integers. Explanation:

Ｎθ


Input x.

⊞υ⟦¹⟧


Start a breadth-first search with the trivial chain of length 1.

ＦυＦ¬⊙υ№κθ


Loop over the search results until a chain is found that includes x.

ＦιＦ⁻⁺⁺ιλ⁻ιλι


Loop over all the sums and differences that aren't already in the chain.

⊞υ⁺ι⟦μ⟧


Push a new chain to the search list.

Ｉ⊟Φυ№ιθ


Print a chain that includes x.

¹Struggles to complete solutions requiring chains of length 6. At a cost of 6 bytes it's possible to speed it up by avoiding pushing duplicate chains to the search list but that's still only enough for it to find all chains of length 6.

• "Start a bread-first search" - one of my favorite snack-searching algorithms. Commented May 17, 2021 at 18:50

# Ruby, 77 bytes

->n,*r{*a=1;(a.product(a){|x,y|r|=[a|[x+y],a|[x-y]]};a,*r=r)until a[-1]==n;a}


Try it online!

# 05AB1E, 22 bytes

X¸¸[ćD©Iå#ãDOsÆ«ε®sª}«


Try it online!

Very slow, the performance can be improved a bit by adding three bytes:

X¸¸[ćD©Iå#ãDOsÆ«®KÙε®sª}«
`

Try it online!