Используйте любое количество каждой из предложенных монет, чтобы получить сумму точно. Считайте комбинации, а не перестановки: два варианта, использующие одинаковое количество каждой монеты, считаются одним способом. Номиналы различны и положительны.
Реализуйте функцию coin_sums(amount, coins).
Входные данные
amount: Сумма, которую нужно получить.
coins: Доступные различные номиналы монет.
Выходные данные
Верните количество неупорядоченных комбинаций.
Ограничения
0 ≤ amount ≤ 200. От 0 до 10 различных номиналов, каждый от 1 до 200. Все значения помещаются в знаковый 64-битный тип. Для суммы 0 существует один способ: не выбирать ни одной монеты.
Примеры
Ввод:
coins = [1, 2]
amount = 4
Ожидаемый вывод:
expected = 3Ввод:
std::vector<long long> coins = {1, 2};
long long amount = 4;
Ожидаемый вывод:
long long expected = 3;Ввод:
long[] coins = new long[] {1, 2};
long amount = 4;
Ожидаемый вывод:
long expected = 3;Пояснение
Комбинации: четыре монеты по 1, две монеты по 1 и одна по 2, и две монеты по 2.
Ввод:
coins = [2]
amount = 3
Ожидаемый вывод:
expected = 0Ввод:
std::vector<long long> coins = {2};
long long amount = 3;
Ожидаемый вывод:
long long expected = 0;Ввод:
long[] coins = new long[] {2};
long amount = 3;
Ожидаемый вывод:
long expected = 0;Пояснение
Любая сумма из монет по 2 будет чётной, поэтому 3 получить невозможно.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Порядок монет не важен, поэтому считайте комбинации по номиналам, а не по перестановкам.
Подсказка 2
Постройте число способов для каждой суммы постепенно, позволяя каждой монете вносить вклад во все достижимые суммы.
Подсказка 3
Осторожно со значением zero: для суммы 0 всегда есть один способ — не брать ни одной монеты.
Ожидаемая сложность
время O(amount × number_of_coins), доп. память O(amount)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.