L'ordre des choix change tout

(* Vrai s'il existe un sous-ensemble de t de somme cible.
   Précondition : les éléments de t sont positifs ou nuls.
   reste.(i) est la somme de t.(i .. n-1), précalculée en Theta(n). *)
let sous_somme t cible =
  let n = Array.length t in
  let reste = Array.make (n + 1) 0 in
  for i = n - 1 downto 0 do reste.(i) <- reste.(i+1) + t.(i) done;
  let trouve = ref false in
  let rec explorer i somme =
    if somme = cible then trouve := true
    else if i < n
            && somme < cible                    (* ÉLAGAGE 1 : déjà dépassé *)
            && somme + reste.(i) >= cible then   (* ÉLAGAGE 2 : plus assez *)
      begin
        explorer (i + 1) (somme + t.(i));
        if not !trouve then explorer (i + 1) somme
      end
  in
  explorer 0 0;
  !trouve

La mesure, sur les seize nombres premiers $11,13,\dots ,71$ (somme totale $622$) :

($45$ est la plus grande valeur inférieure à $311$ que l'on ne peut pas atteindre : elle a été trouvée par énumération de toutes les sommes atteignables.)

Pourquoi le décroissant gagne. Un gros nombre placé tôt fait franchir vite l'un des deux seuils : soit la somme dépasse $c$ et l'élagage 1 mord, soit elle s'en approche et il ne reste plus qu'à ajuster. Avec les petits d'abord, on descend longtemps sans que rien ne tranche.

Et l'ordre ne change rien à la correction : les deux versions rendent la même réponse. C'est une règle générale du retour sur trace — l'ordre des choix est un paramètre d'efficacité, jamais de justesse. On peut donc le régler librement, et le régler est souvent le meilleur investissement : ici, un simple tri divise le travail par cinq.