Coin possible combinations problem
Given :
A => Amount , N=> No of coins , L[N]=> List of Coins
To find :
In how many ways we can make the amount using given coins.
Example:
A=> 5 , N=>4 , L[4]=>1,2,3,5
Answer : 6
1,1,1,1,1,1
2,2,1
2,1,1,1
3,2
3,1,1
5
I wrote this in random order by thinking. Not any steps I followed.
It is easy to calculate for this type of simple example.
Consider This Example. I cannot use my mind like previous one and can get answer . But in case if I calculate this means also a error possibility is very high.
What to do now? 🤔
I split the problem now for my easier calculation.
First let’s consider I having only one rupee coin. Now amount = 100.
Now I easily say there is only one way of getting 100 amount. That is 100 quantity of 1 rupee coin.
Now we got for 1 coin let’s go to next coin 2. How many ways of getting 100 amount. Here also 1 way. 50 quantity of 2 rupee coin.
Shall we go to next coin.. Now calculated answers are seperated We have to combine both first before proceeding to next coin.
Joining means you cannot add like 1way+1way = 2way. That means you have included only
1,1…….1(100 times)
2,2….2( 50 times )
I can distribute also 49 qty of 2rupee and 2 qty of 1rupee. So now we have to include all this combination.
So Again There is Problem. We have to again Split the problem
Think as why I will calculate for 100 rupee. I split this also into minor thing.
Consider the amount = 0
Number of ways in 1 rupee coin 1.
Number of ways in 2 rupee coin 1.
You may think why from amount 0. I will tell later. Amount 0 means nothing. So for all coins the value is constant 1 . You may think also how it is one way when amount is 0. Consider you are shopkeeper you have 1,2 rupee coin. You have to give 0 rupee. How many ways are there
0 qty of 1 Rupee coin That is one way.
0 qty of 2 Rupee coin. That is one way.
So total 1 way because both have 0 qty so 1 way only not 2 way
Consider the amount = 1
Number of ways in 1 rupee coin 0
Number of ways in 2 rupee coin 1
So total 1 possibility.
Consider the amount = 2.
Number of ways in 1 rupee coin 1.
Before calculating for 2 rupee coin we can use older values How?
Subtract Amount-Coin(Now 2)
2–2 = 0
(why 2–2 first 2 is present amount second 2 is coin. So for next 3 rupee it is be like 3–2.)
For 0 Already calculated it is 1 way. So use that. 1 way
so total 2 possibility
Consider The amount = 3
Number of ways in one rupee coin = 1.
Number of ways in two rupee coin
3–2=1.Take the answer of amount 1. It is one way.
So total 2 ways. It goes like this.
You may think how 1 is answer for 3. 2 is answer for 4….
I justify it with example.
Consider the amount 3.
You have to give in 2 rupee.
Take one 2 rupee. Now what is remaining amount 1. So now for amount 1 there is n possible ways.
So we can take that answer.
So it may be little bit confusing to understand for someone what is exactly happening. Take some time and do it on paper. You will understand the dynamic programming methods.
For above problem in Image 1 the answer is
