Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins. The order of coins doesn’t matter .

coin_change.cpp

/*
Coin Change Problem:

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of 
S = { S1, S2, .. , Sm} valued coins. The order of coins doesn’t matter. 
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. 
So output should be 4. 
For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. 
So the output should be 5.
*/
#include <bits/stdc++.h>
using namespace std;

int numWaysToMakeCoinChange(vector<int> &arr , int w)
{
    int n = arr.size() ;
    vector<vector<int> > dp(n+1 , vector<int>(w+1 , 0) );
    for(int i = 0 ; i <= n ; i++)
    {
        for(int j = 0 ; j<=w ; j++)
        {
            if(j == 0)  
                dp[i][j] = 1 ;
            else if(i == 0)
                dp[i][j] = 0 ;
            else if(arr[i-1] <= j)
                dp[i][j] = dp[i-1][j] + dp[i][j-arr[i-1]] ;
            else
                dp[i][j] = dp[i-1][j] ;
            
            //cout<<dp[i][j] << " " ;
        }
        //cout<<"\n" ;
    }
    return dp[n][w] ;
}

int main() {
	//code
	int t ;
	cin>>t ;
	while(t--)
	{
	    int n ;
	    cin>>n ;
	    vector<int> arr ;
	    for(int i = 0 ; i < n ; i++)
	    {
	        int temp ; cin >> temp ;
	        arr.push_back(temp) ;
	    }
	    int w ;
	    cin >> w ;
	    cout<<knapSack(arr , w) << "\n" ;
	}
	return 0;
}