Coin change (II)

Number of possible combinations of coins to obtain a given value

1) Initialize a list that contains the number of possible combination to obtain values between 0 and the amount

2) Initialize every values to 0 expect for 0 that is initialize to 1 (1 possible combination to obtain 0)

3) Iterate over every available coins

4) Iterate over every value of the list

5) For each value we can add the possible combinations to obtain the value minus the current coin to the number of possible combinations for this value

6) Return the number of possible combinations for last value

def change(amount: int, coins: List[int]) -> int:
    combinations = [1] + [0 for _ in range(amount)] # list initialisation to 0 except 0 to 1
    for coin in coins:
        for i in range(coin, len(combinations)):
            combinations[i] += combinations[i-coin] # add number of combination for i-coin
    return(combinations[-1])