494. Somme cible

494. Somme cible

Difficulté : moyenne

Sujets :Tableau,Programmation dynamique,Retour en arrière

On vous donne un tableau d'entierschiffreset un entiercible.

Vous souhaitez créer une expression à partir de nombres en ajoutant l'un des symboles'+'et'-'avant chaque entier en nombres, puis concaténer tous les entiers.

• Par exemple, sinombres = [2, 1], vous pouvez ajouter un'+'avant2et un'-'avant1et concaténez-les pour construire l'expression"+2-1".

Renvoie le nombre d'expressions différentes que vous pouvez créer, ce qui donnecible.

Exemple 1 :

• Entrée : nombres = [1,1,1,1,1], cible = 3
• Sortie : 5
• Explication : Il existe 5 façons d'attribuer des symboles pour que la somme des nombres soit la cible 3.
  • -1 + 1 + 1 + 1 + 1 = 3
  • +1 - 1 + 1 + 1 + 1 = 3
  • +1 + 1 - 1 + 1 + 1 = 3
  • +1 + 1 + 1 - 1 + 1 = 3
  • +1 + 1 + 1 + 1 - 1 = 3

Exemple 2 :

• Entrée : nombres = [1], cible = 1
• Sortie : 1

Contraintes :

• 1 <= nombres.longue...
[Courte citation de 8% de l'article original]