5819. Число способов набрать сумму
Medium
0 решили
Есть монеты номиналов
Порядок монет не важен: 1 и 2 — тот же способ, что 2 и 1. Верните, сколько таких способов. Если сумму набрать нельзя, ответ 0. Если
Нужно именно число способов, а не наименьшее количество монет.
coins. Каждого номинала сколько угодно, сами номиналы не повторяются. Нужно набрать сумму ровно amount.Порядок монет не важен: 1 и 2 — тот же способ, что 2 и 1. Верните, сколько таких способов. Если сумму набрать нельзя, ответ 0. Если
amount равен 0, способ один — не брать ни одной монеты.Нужно именно число способов, а не наименьшее количество монет.
Примеры:
Вход:
coins = [1, 2, 5], amount = 5
Выход:
4
Объяснение: Четыре способа: 5; 2+2+1; 2+1+1+1; пять единиц. 2+1 и 1+2 — один способ.
Вход:
coins = [2], amount = 3
Выход:
0
Объяснение: Двойками тройку не набрать.
Вход:
coins = [1, 2], amount = 0
Выход:
1
Объяснение: Ни одной монеты — уже подходящий способ.
Ограничения:
1 <= coins.length <= 100
1 <= coins[i] <= 5000
номиналы различны
0 <= amount <= 5000
ответ помещается в 32-битное целое
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python и Java, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!