Conta le Combinazioni di Monete

Usa qualsiasi numero di ciascuna denominazione fornita per ottenere esattamente l'importo richiesto. Conta le combinazioni, non le disposizioni: due modi che usano lo stesso numero di ciascuna moneta sono considerati uguali. Le denominazioni sono distinte e positive.

Implementa coin_sums(amount, coins).

Input

amount: L'importo totale da ottenere.

coins: Le denominazioni distinte disponibili.

Output

Restituisci il numero di combinazioni non ordinate.

Vincoli

0 ≤ amount ≤ 200. Ci sono da 0 a 10 denominazioni distinte, ciascuna compresa tra 1 e 200. Tutti i conteggi rientrano in un intero con segno a 64 bit. Per amount 0 esiste un solo modo: non scegliere nessuna moneta.

Esempi

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

Output atteso:
expected = 3

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

Output atteso:
long long expected = 3;

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

Output atteso:
long expected = 3;

Input:
coins = [2]
amount = 3

Output atteso:
expected = 0

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

Output atteso:
long long expected = 0;

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

Output atteso:
long expected = 0;

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

• #31 Coin Sums