Дан набор номиналов монет и целевая сумма. Напиши функцию, которая вычисляет общее количество различных комбинаций для составления этой суммы.

Обзор задачи

Задача Coin Change Combinations звучит так: дан список номиналов монет и целевая сумма, сколько различных комбинаций монет дают эту сумму?

Подход: динамическое программирование

Решение использует таблицу DP «снизу вверх», где dp[i] представляет количество различных способов составить сумму i.

Ключевые детали реализации

• dp[0] = 1 — это базовый случай — существует ровно один способ составить сумму ноль: не использовать никакие монеты
• Внешний цикл проходит по каждому номиналу монеты
• Внутренний цикл обновляет таблицу для всех сумм от coin до amount
• На каждом шаге dp[i] += dp[i - coin] означает: «добавь количество способов получить оставшуюся сумму после использования этой монеты»
• Перебор монет во внешнем цикле гарантирует, что каждая комбинация считается только один раз, исключая дубликаты вроде [1,2] и [2,1]

Сложность

• Временная сложность: O(n * m), где n — целевая сумма, m — количество номиналов
• Пространственная сложность: O(n) для таблицы DP

Пример

Для номиналов [1, 2, 3] и суммы 4 результат равен 4:

• [1,1,1,1], [1,1,2], [1,3], [2,2]