Somme des Sous-ensembles
Algorithmique classique
Enonce
Déterminer s'il existe un sous-ensemble de L dont la somme vaut exactement cible.
Signature attendue
def somme_sous_ensembles(L: list, cible: int) -> bool:Exemples
somme_sous_ensembles([3, 34, 4, 12, 5, 2], 9)→True (4+5)somme_sous_ensembles([3, 34, 4, 12, 5, 2], 30)→Falsesomme_sous_ensembles([1, 2, 3], 6)→True
📖 Rappel de cours
Pour chaque élément, on essaie de le prendre ou non, et on regarde si la cible restante peut être atteinte avec le reste de la liste.
⚠ Le piège : Deux cas de base : cible atteinte à zéro, c'est gagné ; plus d'éléments alors que la cible n'est pas nulle, c'est perdu. Les oublier fait explorer indéfiniment.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Permutations d'une Liste
- Combinaisons de k parmi n
- Flocon de Koch (coordonnées)
- Fibonacci par Programmation Dynamique
- Sac à Dos 0/1
- Plus Longue Sous-séquence Commune (LCS)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.