Problema
Usa cualquier cantidad de cada denominación suministrada para obtener exactamente la cantidad indicada. Cuenta combinaciones, no ordenamientos: dos arreglos que usan la misma cantidad de cada moneda se consideran la misma forma. Las denominaciones son distintas y positivas.
Implementa coin_sums(amount, coins).
Entrada
amount: La cantidad total a obtener.
coins: Las denominaciones distintas disponibles.
Salida
Devuelve el número de combinaciones sin importar el orden.
Restricciones
0 ≤ amount ≤ 200. Hay entre 0 y 10 denominaciones distintas, cada una entre 1 y 200. Todos los conteos caben en un entero con signo de 64 bits. Para amount 0 hay una forma: no elegir ninguna moneda.
Ejemplos
Entrada:
coins = [1, 2]
amount = 4
Salida esperada:
expected = 3Entrada:
std::vector<long long> coins = {1, 2};
long long amount = 4;
Salida esperada:
long long expected = 3;Entrada:
long[] coins = new long[] {1, 2};
long amount = 4;
Salida esperada:
long expected = 3;Explicación
Las combinaciones son: cuatro monedas de 1, dos monedas de 1 con una de 2, y dos monedas de 2.
Entrada:
coins = [2]
amount = 3
Salida esperada:
expected = 0Entrada:
std::vector<long long> coins = {2};
long long amount = 3;
Salida esperada:
long long expected = 0;Entrada:
long[] coins = new long[] {2};
long amount = 3;
Salida esperada:
long expected = 0;Explicación
Cualquier suma usando solo monedas de valor 2 es par, así que 3 es imposible.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
El orden de las monedas no importa, así que las combinaciones deben contarse por denominación, no por permutación.
Pista 2
Construye el número de formas para cada cantidad de manera incremental, dejando que cada moneda contribuya a todos los totales alcanzables.
Pista 3
Ten cuidado con la cantidad cero, que siempre tiene una forma válida: no elegir monedas.
Complejidad esperada
tiempo O(amount × number_of_coins), espacio extra O(amount)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.