Bonjour,
Je poste ici pour demander de l'aide, je m'intéresse à un certain problème que je voudrais résoudre mais je n'y arrive pas.
Le problème est : imaginons une liste [ 2,4,5,6,8,10,7] et une variable qu'on désire, exemple : n = 10
Je voudrais trouver de manière récursive, une fonction qui renvoie l'ensemble des choix des nombres de la liste dont la somme = n
Mais on peut prendre plusieurs fois le même élément.
Exemple pour la liste[ 2,4,5,6,8,10,7] et n =10
On pourrait avoir comme réponse :
[(5*2),(2*4 +2),(2*5),(6+4),(6+2*2),(8+2),(10)] et il se peut que j'ai oublié certaines réponses
Merci de votre aide

Ben pour chaque élément k de ta liste (si k <= n), si tu choisis d'utiliser k, il te reste à chercher récursivement toutes les possibilités pour faire (n - k) avec ta liste.

Fais attention aux éventuels doublons (soit dans ta liste de départ, soit que tu vas éventuellement générer suivant comment tu t'y prends).

Et puis je sais pas pour quelle raison tu veux faire ça exactement, mais ta fonction n'est pas très bien définie s'il y a des nombres négatifs et positifs dans ta liste ça risque de faire une infinité de solutions

J'avais pas pensé à faire par soustraction... Je vais essayer, mais je suis encore ouvert à toute proposition
Merci !
Mais non, il n'y a que des nombre > 0 dans la liste, afin d'éviter justement la boucle infini

Je te conseille de t'intéresser au techniques dites de backtracking. Ici, tu backtrack si la somme des éléments restants dans ta liste est inférieure au nombre n désiré. J'ai un code qui fait exactement ce que tu cherches à faire, si tu y arrives toujours pas redis-le.

J'y suis parvenu via backtracking en effet, merci

Utilise Prolog et c'est terminé en 10 minutes

10 minutes c'est le temps que met ton programme à tourner sur une instance de taille 10 non ?