Fun! I'll try explain my thought process through my 3 iterations so far, and include some timing examples.

First off, I realized that when adding the two numbers, one of those two can always be the most recent in the chain (at least it worked for all the examples, not completely convinced it's true...). From there I decided I would count up, using the minimum addition every time (1), and increasing to the next smallest number in the last place of the chain until it rolled over, repeating. e.g. 1,2,3,4 -> 1,2,3,5 -> 1,2,3,6 -> 1,2,4,5 -> 1,2,4,6 -> etc. (not sure why I chose to start up, down would be faster). I banged out my first solution using this fairly brute force method. add_chain_0.c

It works! It's a little slow but it works! Next up I needed some heuristic to cut down on the number of combinations I tried, some way to prune the recursive tree. I came to the conclusion that the fastest we can grow is powers of 2 by constantly doubling the most recent number in the chain. For any number n in position i of chain length l, the largest number we can get to is n * 2 ^ (l - i). If that number is smaller than our goal, we don't have to continue down this path, we can just stop now and work on a better one. It works! It's a lot faster! add_chain_1.c

It wasn't until this point that I realized it may be faster to use the largest numbers possible first. I wasn't sure it would be faster, didn't have any proof, so I tried it. It's even faster!! add_chain_2.c

Here are some timing results (I didn't do 19 123456 for the first implementation because I'm very impatient). I also kept track of how many times I recursed into solve() as a more objective measurement of performance. The pruning makes a huge difference, and the order of addition has a smaller but still noticeable effect. (I replaced the newlines with commas for the results so it's more compact)

[Ynsolti tidbits 330 130]$ for a in add_chain_[012]; do echo "$a"; time ./"$a" 13 743; done
add_chain_0
1,2,3,4,7,8,15,23,46,92,184,368,375,743,
8460485791 calls

real    0m25.059s
user    0m25.057s
sys     0m0.000s
add_chain_1
1,2,3,4,7,8,15,23,46,92,184,368,375,743,
42205838 calls

real    0m0.130s
user    0m0.127s
sys     0m0.000s
add_chain_2
1,2,4,8,16,32,64,128,160,162,290,580,742,743,
3493266 calls

real    0m0.011s
user    0m0.010s
sys     0m0.000s
[Ynsolti tidbits 330]$ for a in add_chain_[12]; do echo "$a"; time ./"$a" 19 123456; done
add_chain_1
1,2,3,5,10,20,40,80,160,320,323,643,1286,1929,3858,7716,15432,30864,61728,123456,
73991765 calls

real    0m0.259s
user    0m0.257s
sys     0m0.000s
add_chain_2
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,8256,16448,32896,41152,82304,123456,
8448496 calls

real    0m0.027s
user    0m0.023s
sys     0m0.000s

25 1234567 is still running. I don't think it will stop any time soon. I'm off to see if I can think of a way to store intermediate results that would be helpful. As a fun aside I realized that changing solve() to still return 0 when it finds a successful chain will cause it to print out all valid chains of the given length. Enjoy!