F# alternative solution to these ones: http://blog.bjartwolf.com/?p=4272

Problem5.fs

type Expr = Number of int | Plus of Expr * int | Minus of Expr * int

let rec eval = function 
  | Number n -> n
  | Plus(e, n) -> (eval e) + n
  | Minus(e, n) -> (eval e) - n

let rec exprAsString = function 
  | Number n -> n.ToString()
  | Plus(e, n) -> sprintf "%s + %d" (exprAsString e) n
  | Minus(e, n) -> sprintf "%s - %d" (exprAsString e) n
  
let mapIntegerPart f = function
  | Number n -> Number(f n)
  | Plus(e, n) -> Plus(e, f n)
  | Minus(e, n) -> Minus(e, f n)

///Generate all possible expressions of digits from 1 to n
let rec generateExprs n = 
  seq { 
    match n with
    | 1 -> yield Number(1)
    | t when t > 1 -> 
      let prevExprs = generateExprs (n - 1)
      for prevExpr in prevExprs do
        yield prevExpr |> mapIntegerPart (fun prev_n -> prev_n * 10 + n) //"Concat" in the new digit
        yield Plus(prevExpr, n)
        yield Minus(prevExpr, n)
    | _ -> failwith "Invalid parameter, must be >=1"
  }
      
let generateAndPrintSolutions() = 
  generateExprs 9 |> Seq.filter(fun expr-> (eval expr)=100) |> Seq.map exprAsString |> Seq.iter (printfn "%s")

https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions

Can you run it and post how many solutions?

Output:
123 + 45 - 67 + 8 - 9
123 + 4 - 5 + 67 - 89
123 - 45 - 67 + 89
123 - 4 - 5 - 6 - 7 + 8 - 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
1 + 23 - 4 + 56 + 7 + 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9

Performance: Takes 2 milliseconds to run it on my machine in f#-interactive.
(Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0)

A "clever" (both slower and much harder to understand) solution is here:
https://gist.github.com/jarlestabell/bec41f108c0715bfbc68