Somme combinée II

40. Somme combinée II

Difficulté :Moyen

Sujets :Array, Backtracking

Étant donné une collection de numéros de candidats (candidats) et un numéro cible (cible), trouvez toutes les combinaisons uniques de candidats où la somme des numéros de candidats correspond à la cible.

Chaque numéro des candidats ne peut être utilisé une fois dans la combinaison.

Remarque : L'ensemble de solutions ne doit pas contenir de combinaisons en double.

Exemple 1 :

• Entrée : candidats = [10,1,2,7,6,1,5], cible = 8
• Sortie : [[1,1,6], [1,2,5], [1,7], [2,6]]

Exemple 2 :

• Entrée : candidats = [2,5,2,1,2], cible = 5
• Sortie : [[1,2,2], [5]]

Contraintes :

• 1 <= candidats.length <= 100
• 1 <= candidats[i] <= 50
• 1 <= cible <= 30

Solution :

Nous pouvons utiliser une approche de retour en arrière. L'idée clé est de trier d'abord le tableau pour gérer facilement les doublons, puis d'explorer toutes les combinaisons possibles en utilisant le backtracking.

Implémentons cette solution en PHP : 40. Somme combinée II

Explication:

1. Tri : le tableau des candidats est trié pour gérer facilement les doublons et garantir que les combinaisons sont formées dans un ordre trié.
2. Backtracking : La fonction backtracking permet d'explorer toutes les combinaisons possibles.
   • Si la cible devient nulle, nous ajoutons la combinaison actuelle au résultat.
   • Nous parcourons les candidats à partir de l'index actuel. Si un candidat est le même que le précédent, nous le sautons pour éviter les combinaisons en double.
   • Nous soustrayons le candidat actuel de la cible et appelons récursivement la fonction backtrack avec la nouvelle cible et l'index suivant.
   • L'appel récursif continue jusqu'à ce que nous trouvions une combinaison valide ou que nous épuisions toutes les possibilités.
3. Élagage : Si le candidat dépasse l'objectif, nous sortons de la boucle plus tôt car d'autres candidats dépasseront également l'objectif.

Ce code affichera toutes les combinaisons uniques qui correspondent à l'objectif tout en garantissant que chaque candidat n'est utilisé qu'une seule fois dans chaque combinaison.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!