Here's a probably quite slow alternative
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[Append[arg1, First@arg2], Rest@arg2]; flatten[exp_] := Flatten@Cases[exp, {_}, {0, Infinity}] search[l_, target_] := Module[{curr = l, tag}, Reap[ Quiet[ While[curr =!= False, If[ReleaseHold[curr /. List -> Composition[FromDigits, List]] == target, PrintTemporary@Sow[ curr /. {i_List :> FromDigits@i, HoldForm[Plus] -> next`Plus, HoldForm[Times] -> next`Times, HoldForm[Subtract] -> (next`Plus[#1, Times[-1, #2]] &), HoldForm[Divide] -> next`Divide},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 way less-slow