Reconstruire le sous-ensemble

let rec trouve_somme l cible =
  if cible = 0 then Some []
  else
    match l with
    | [] -> None
    | x :: reste ->
        match trouve_somme reste (cible - x) with
        | Some s -> Some (x :: s)            (* x fait partie de la solution *)
        | None -> trouve_somme reste cible   (* sinon, chercher sans x *)

On essaie d'abord de prendre x : si la suite réussit, on l'ajoute à la solution rapportée ; sinon, on cherche sans lui. Le type option porte à la fois l'échec (None) et la solution reconstruite (Some s) — le backtracking « remonte » la solution le long des choix réussis.