<p>You are given an integer array <code>coins</code> representing coins of different denominations and an integer <code>amount</code> representing a total amount of money.</p>

<p>Return <em>the number of combinations that make up that amount</em>. If that amount of money cannot be made up by any combination of the coins, return <code>0</code>.</p>

<p>You may assume that you have an infinite number of each kind of coin.</p>

<p>The answer is <strong>guaranteed</strong> to fit into a signed <strong>32-bit</strong> integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> amount = 5, coins = [1,2,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> amount = 3, coins = [2]
<strong>Output:</strong> 0
<strong>Explanation:</strong> the amount of 3 cannot be made up just with coins of 2.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> amount = 10, coins = [10]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= coins.length &lt;= 300</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 5000</code></li>
	<li>All the values of <code>coins</code> are <strong>unique</strong>.</li>
	<li><code>0 &lt;= amount &lt;= 5000</code></li>
</ul>

class Solution {
    int countWaysToMakeChangeUtil(vector<int>& arr, int ind, int T, vector<vector<int>>& dp) {
    // Base case: if we're at the first element
    if (ind == 0) {
        // Check if the target sum is divisible by the first element
        return (T % arr[0] == 0);
    }
    
    // If the result for this index and target sum is already calculated, return it
    if (dp[ind][T] != -1)
        return dp[ind][T];
        
    // Calculate the number of ways without taking the current element
    long notTaken = countWaysToMakeChangeUtil(arr, ind - 1, T, dp);
    
    // Calculate the number of ways by taking the current element
    long taken = 0;
    if (arr[ind] <= T)
        taken = countWaysToMakeChangeUtil(arr, ind, T - arr[ind], dp);
        
    // Store the sum of ways in the DP table and return it
    return dp[ind][T] = notTaken + taken;
}

    long countWaysToMakeChange(vector<int>& arr, int n, int T) {
        vector<vector<long>> dp(n, vector<long>(T + 1, 0)); // Create a DP table

        // Initializing base condition
        for (int i = 0; i <= T; i++) {
            if (i % arr[0] == 0)
                dp[0][i] = 1;
            // Else condition is automatically fulfilled,
            // as dp array is initialized to zero
        }

        for (int ind = 1; ind < n; ind++) {
            for (int target = 0; target <= T; target++) {
                long notTaken = dp[ind - 1][target];

                long taken = 0;
                if (arr[ind] <= target)
                    taken = dp[ind][target - arr[ind]];

                dp[ind][target] = notTaken + taken;
            }
        }

        return dp[n - 1][T];
    }

    long countWaysToMakeChangeSO(vector<int>& arr, int n, int T) {
        vector<long> prev(T + 1, 0);  // Create a vector to store the previous DP state

        // Initialize base condition
        for (int i = 0; i <= T; i++) {
            if (i % arr[0] == 0)
                prev[i] = 1;  // There is one way to make change for multiples of the first coin
            // Else condition is automatically fulfilled,
            // as the prev vector is initialized to zero
        }

        for (int ind = 1; ind < n; ind++) {
            vector<long> cur(T + 1, 0);  // Create a vector to store the current DP state
            for (int target = 0; target <= T; target++) {
                long notTaken = prev[target];  // Number of ways without taking the current coin

                long taken = 0;
                if (arr[ind] <= target)
                    taken = cur[target - arr[ind]];  // Number of ways by taking the current coin
                    
                cur[target] = notTaken + taken;  // Total number of ways for the current target
            }
            prev = cur;  // Update the previous DP state with the current state for the next coin
        }

        return prev[T];  // Return the total number of ways to make change for the target
    }

public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        // vector<vector<int>> dp(n, vector<int>(amount + 1, -1)); // Create a DP table
    
        // // Call the utility function to calculate the answer
        // return countWaysToMakeChangeUtil(coins, n - 1, amount, dp); 

        return countWaysToMakeChangeSO(coins, n, amount);
    }
};
29995