Maison  >  Article  >  développement back-end  >  Somme combinée II

Somme combinée II

WBOY
WBOYoriginal
2024-08-14 10:38:41825parcourir

Combination Sum 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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn