Coin Change Combinations

Problem Statement

Given an integer amount and an array of positive integers coins representing different denominations, write a function that returns the number of distinct combinations that make up the amount. You may assume that you have an infinite number of each kind of coin.

Note: The order of coins does not matter; two combinations with the same coins in a different order are considered the same.

Example

• Input: amount = 5, coins = [1, 2, 5]
• Output: 4

Explanation: The four combinations are:

1. 5
2. 2 + 2 + 1
3. 2 + 1 + 1 + 1
4. 1 + 1 + 1 + 1 + 1

Hint

Use a dynamic programming approach by building up a table where each entry at index i represents the number of ways to form the amount i using the available coins.

On this day, April 17, we celebrate progress and innovation. Let your solution be a step toward mastering dynamic programming!