Problème
Utilisez autant de chaque valeur fournie que nécessaire pour former exactement le montant. Comptez les combinaisons, pas les arrangements : deux façons utilisant le même nombre de chaque pièce comptent comme une seule combinaison. Les valeurs sont distinctes et strictement positives.
Implémentez coin_sums(amount, coins).
Entrée
amount : Le montant total à former.
coins : Les valeurs distinctes disponibles.
Sortie
Retournez le nombre de combinaisons sans ordre.
Contraintes
0 ≤ amount ≤ 200. Il y a de 0 à 10 valeurs distinctes, chacune comprise entre 1 et 200. Tous les résultats tiennent dans un entier signé 64 bits. Pour amount = 0, il existe une seule façon : ne choisir aucune pièce.
Exemples
Entrée :
coins = [1, 2]
amount = 4
Sortie attendue :
expected = 3Entrée :
std::vector<long long> coins = {1, 2};
long long amount = 4;
Sortie attendue :
long long expected = 3;Entrée :
long[] coins = new long[] {1, 2};
long amount = 4;
Sortie attendue :
long expected = 3;Explication
Les combinaisons sont : quatre pièces de 1, deux pièces de 1 avec une pièce de 2, et deux pièces de 2.
Entrée :
coins = [2]
amount = 3
Sortie attendue :
expected = 0Entrée :
std::vector<long long> coins = {2};
long long amount = 3;
Sortie attendue :
long long expected = 0;Entrée :
long[] coins = new long[] {2};
long amount = 3;
Sortie attendue :
long expected = 0;Explication
Toute somme de pièces de valeur 2 est paire, donc 3 est impossible.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
L’ordre des pièces ne compte pas, donc il faut compter les combinaisons par dénomination, pas les permutations.
Indice 2
Construis le nombre de façons pour chaque montant progressivement, en laissant chaque pièce contribuer à tous les totaux atteignables.
Indice 3
Attention au montant zéro, qui a toujours une seule façon valide : ne prendre aucune pièce.
Complexité attendue
temps O(amount × number_of_coins), espace supplémentaire O(amount)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.