# Coin Change-no of ways to get a total

given some coins with infinite supply . we have to find the number of ways to get a given total(sum).

example

n=3

coins={1,2,3}

sum=5

1 1 1 1 1 --- 1st

1 1 1 2 --- 2nd

1 1 3 --- 3rd

2 3 --- 4th

1 1 2 --- 5th

we will use dynamic programming to solve this question:

y is no. of test cases

n is no of different coins

a[] array to store coins

c++ implementation:

example

n=3

coins={1,2,3}

sum=5

**output => 5**(total ways)1 1 1 1 1 --- 1st

1 1 1 2 --- 2nd

1 1 3 --- 3rd

2 3 --- 4th

1 1 2 --- 5th

we will use dynamic programming to solve this question:

y is no. of test cases

n is no of different coins

a[] array to store coins

c++ implementation:

**#include <iostream>
using namespace std;
void coins(int a[],int n,int sum)
{
int t[n+1][sum+1];
for(int i=0;i<=n;i++)
t[i][0]=1;
for(int j=1;j<=sum;j++)
t[0][j]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum;j++)
{
if(a[i-1]>j)
t[i][j]=t[i-1][j];
else
t[i][j]=t[i][j-a[i-1]]+t[i-1][j];
}
}
cout<< t[n][sum];
}
int main() {
int y; cin>>y;
while(y--)
{ int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int sum;
cin>>sum;
coins(a,n,sum);
cout<<endl;
}
return 0;
}**