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")

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