given some coins with infinite supply . Find the minimum number of coins to make the 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
these are the total ways . in this the minimum is 4th ie, (2,3) which contains two coins
so output=>2

if not possible print "-1".

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 mincoins(int a[],int n,int sum)
{
int t[n+1][sum+1];

for(int i=0;i<=n;i++)
t[i]=0;

for(int j=1;j<=sum;j++)
t[j]=10000;

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]=min(t[i][j-a[i-1]]+1,t[i-1][j]);

}
}

if(t[n][sum]==10000)
cout<<-1;
else
cout<<t[n][sum];
}

int main() {
int y; cin>>y;
while(y--)
{  int sum;   cin>>sum;

int n;   cin>>n;

int a[n];
for(int i=0;i<n;i++)
cin>>a[i];

mincoins(a,n,sum);
cout<<endl;
}
return 0;
}```

darkmode