<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>

//Approch 1
class Solution {
public:
    /*this code find ways and its combination in ques we have to not find combination*/
    int solve(vector<int>&arr,int target,vector<int> path) {
        int n=arr.size();
        if(target==0) {
            for(auto &x:path) {
                cout<<x<<" ";
            }cout<<endl;
            return 1;
        }
        if(target<0) {
            return 0;
        }
        int ans=0;
        for(int i=0;i<n;i++) {
            path.push_back(arr[i]);
            ans+=solve(arr,target-arr[i],path);
            path.pop_back();
        }
        return ans;
    }
    int dp[301][5001];
    int solve2(vector<int>&arr,int index,int target) {
        if(index>=arr.size()) {
            return target==0;
        }
        if(target==0) {
            return 1;
        }
        if(dp[index][target]!=-1) {
            return dp[index][target];
        }
        int take=0;
        int not_take=solve2(arr,index+1,target);
        if(target-arr[index]>=0) {
            //here by not change index we take all arr[i] coin at once
            take=solve2(arr,index,target-arr[index]);
        }
        return dp[index][target]=take+not_take;
    }

    int tab(vector<int>&arr,int amount) {
        int n=arr.size();
        vector<vector<int>>dp(n+1,vector<int>(amount+1,0));
        for(int i=0;i<=n;i++) {
            dp[i][0]=1;
        }
        for(int index=n-1;index>-1;index--) {
            for(int target=0;target<=amount;target++) {
                int take=0;
                int not_take=dp[index+1][target];
                if(target-arr[index]>=0) {
                    //here by not change index we take all arr[i] coin at once
                    take=dp[index][target-arr[index]];
                }
                dp[index][target]=take+not_take;
            } 
        }
        return dp[0][amount];
    }

    int change(int amount, vector<int>& coins) {
        // memset(dp,-1,sizeof(dp));
        // int ans=solve2(coins,0,amount);
        int ans=tab(coins,amount);
        return ans;
    }
};
26515