Nombre de façons de rendre

let nb_facons pieces montant =
  let dp = Array.make (montant + 1) 0 in
  dp.(0) <- 1;
  List.iter (fun p ->
    for s = p to montant do
      dp.(s) <- dp.(s) + dp.(s - p)
    done
  ) pieces;
  dp.(montant)

On traite les pièces l'une après l'autre (boucle externe sur pieces) pour ne compter chaque combinaison qu'une fois (et non chaque permutation). dp.(0) = 1 : une seule façon de rendre $0$ (ne rien donner).