LC 0518 [M] Coin Change II 2 (num ways to make amount) - ALawliet/algorithms GitHub Wiki

• combination sum

classic unbounded knapsack

collect the ways as we go through the denoms

the trick here is if we initialize T[0] = 1 (there is only 1 way to make 0, take nothing) this also gives us the += case when the denom == i e.g. we can use 5 at index 5

[1 0 0 0 0 1 0 0 0 0 1](/ALawliet/algorithms/wiki/1-0-0-0-0-1-0-0-0-0-1)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        T = [0] * (amount + 1)
        
        T[0] = 1
        
        for c in coins:
            for a in range(1, amount + 1):
                if c <= a:
                    T[a] += T[a - c]
                    
        return T[-1]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        T = [0] * (amount + 1)

        T[0] = 1

        for denom in coins:
            for a in range(1, amount + 1):
                if denom <= a:
                  T[a] += T[a - denom]
                
        return T[-1]