Here's a probably quite slow alternativepossibility
next`ops = HoldForm /@ {Plus, Times, Divide, Subtract}; (nextOp[#1] = #2) & @@@ Most@Transpose@{next`ops, RotateLeft@next`ops}; next`children = True; SetAttributes[{next`Plus, next`Times}, Flat]; next[{i_}] := False; next[l_List] := HoldForm[Plus][{l[[1]]}, l[[2 ;;]]]; next[op_[arg1_, arg2_]] /; next`children := With[{res = next[arg1]}, op[res, arg2] /; res =!= False]; next[op_[arg1_, arg2_]] /; next`children := With[{res = next[arg2]}, op[arg1, res] /; res =!= False]; next[HoldForm[Subtract][arg1_, arg2 : {_}]] := False; next[op_[arg1_, arg2_]] := Block[{next`children = False}, next[op[flatten@arg1, flatten@arg2]]]; next[op_[arg1_List, {arg2_}]] := nextOp[op][{arg1[[1]]}, arg1[[2 ;;]]~Append~arg2]; next[op_[arg1_List, arg2_List]] := op[arg1~Append~First@arg2, Rest@arg2]; flatten[exp_] := Flatten@Cases[exp, {_}, {0, Infinity}] next is a function that receives a current candidate expression of the form HoldForm[operator][...] where the ultimate integers are introduced as a list of digits, and returns the next candidate to try in the same format, or False if there are no more.
Defining
formattingRules = {i : {__Integer} :> FromDigits@i, HoldForm[Plus] -> next`Plus, HoldForm[Times] -> next`Times, HoldForm[Subtract] -> (next`Plus[#1, Times[-1, #2]] &), HoldForm[Divide] -> next`Divide}; try
NestList[next, Range[9], 30] /. formattingRules // Column To search
doMath[expr_] := expr /. List -> Composition[FromDigits, List] // ReleaseHold search[l_, target_] := Module[{curr = l, tag}, Reap[Quiet[ While[curr =!= False, If[doMath@curr == target, PrintTemporary@Sow[curr /. formattingRules, tag]]; curr = next@curr], Divide::infy], tag][[-1, 1]] // DeleteDuplicates] Now you do
search[Range[9], 100] After 25 minutes I got 2145 solutions. Speed wasn't on my mind when I coded this, so surely it can be made faster. As it is, it prints temporarily the partial results, including a few duplicates due to the associative property of Plus and Times. Perphaps you want to remove that PrintTemporary behaviour or change it to an option. The final result has these duplicates removed. It also outputs the subtraction as "+ -". This can also be fixed without much work. The output cell can be evaluated to verify the results