Münzkombinationen zählen

Verwende beliebig viele Münzen jeder angegebenen Stückelung, um den Betrag exakt zu erreichen. Es sollen Kombinationen gezählt werden, nicht Anordnungen: Zwei Zusammenstellungen mit denselben Anzahlen jeder Münze gelten als dieselbe Möglichkeit. Die Stückelungen sind verschieden und positiv.

Implementiere coin_sums(amount, coins).

Eingabe

amount: Der zu bildende Gesamtbetrag.

coins: Die verfügbaren, verschiedenen Stückelungen.

Ausgabe

Gib die Anzahl der ungeordneten Kombinationen zurück.

Einschränkungen

0 ≤ amount ≤ 200. Es gibt 0 bis 10 verschiedene Stückelungen, jede im Bereich von 1 bis 200. Alle Anzahlen passen in ein vorzeichenbehaftetes 64-Bit-Integer. Für amount 0 gibt es genau eine Möglichkeit: keine Münzen wählen.

Beispiele

Eingabe:
coins = [1, 2]
amount = 4

Erwartete Ausgabe:
expected = 3

Eingabe:
std::vector<long long> coins = {1, 2};
long long amount = 4;

Erwartete Ausgabe:
long long expected = 3;

Eingabe:
long[] coins = new long[] {1, 2};
long amount = 4;

Erwartete Ausgabe:
long expected = 3;

Eingabe:
coins = [2]
amount = 3

Erwartete Ausgabe:
expected = 0

Eingabe:
std::vector<long long> coins = {2};
long long amount = 3;

Erwartete Ausgabe:
long long expected = 0;

Eingabe:
long[] coins = new long[] {2};
long amount = 3;

Erwartete Ausgabe:
long expected = 0;

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

• #31 Coin Sums