Coin Change II (Leetcode 518)

Remember: This is Unbounded Knapsack pattern + Subsets pattern

Problem Link: https://leetcode.com/problems/coin-change-ii/

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        n=len(coins)
        dp=[[0 for i in range(amount+1)] for j in range(n+1)]
        # Note the below two for loops.
        # That means, we cannot consider an empty set
        for i in range(n+1):
            dp[i][0]=1
        for i in range(amount+1):
            dp[0][i]=0
        for i in range(1,n+1):
            for j in range(1,amount+1):
                
                if(coins[i-1]<=j):
                    inc=dp[i][j-coins[i-1]]
                    exc=dp[i-1][j]
                    dp[i][j]=inc+exc
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[n][amount]