Coin Change Combination Problem Dynamic Programming Explained | Coin Change Minimum Number of Coins

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the solution for the coin change combination problem where we need to find the combinations of numbers which sum up to a certain target where each number can be used repetitively. In this problem,
1. You are given a number n, representing the count of coins.
2. You are given n numbers, representing the denominations of n coins.
3. You are given a number "amt".
4. You are required to calculate and print the number of combinations of the n coins using which the amount "amt" can be paid.
Note1 - You have an infinite supply of each coin denomination i.e. same coin denomination can be used for many installments in payment of "amt"
Note2 - You are required to find the count of combinations and not permutations i.e.
2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same combination. You should treat them as 1 and not 3.
For a better understanding of the problem, click here: • Coin Change Combinatio...
For a better experience and more exercises, VISIT: www.pepcoding....
#pepcoding #java #programming
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@arvindg553]

Watching 10 video of this channel and making notes has made me 10 times better coder No endorsement, this is real truth

[@Pepcoding]

keep motivating, keep learning and keep loving Pepcoding😊

[@abhinandanjain5090]

Let us all bow down to his genius explainations! 🙌

[@rohanray3428]

i dont understand why only 846 likes and 29598 views on this video... all videos of pepcoding deserve much much more than this

[@Rohit_Negi]

From your video, we are actually learning, how dp is working.

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@sumitshokeen4065]

Arey Rohit sir aap yha.....

[@sushyyyyyyyy]

@@sumitshokeen4065 haha, i noticed that too!

[@ridhiagarwal1714]

Best explanation that i have came across so far especially for DP.

[@ayyappareddy4461]

thank you sir the way you are explaining problems is easy to understand . untill now i did not find a teacher like you sir. .thank you sir

[@kushagra4401]

because of following your playlist, I was able to do this question without even watching the video. thank you so much sir.

[@rahulsureka]

sir, Your videos are really awesome. I have now modified my search from "question name" to "Question name pepcoding". Thankyou.

[@everyday___life]

Respect. I was stuck on this problem since 3 days. Although I copied the code from somewhere, I wanted to know why the code was working and I landed here. Thanks for explaining in Hindi.

[@Pepcoding]

Glad it helped

[@atishyadavit1036]

You are the best, by god's grace i am lucky that i found you DP playlist, because of your dry run it clears my concept really well. Thank You

[@Pepcoding]

Glad to know that you liked the content and thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating, keep learning and keep loving Pepcoding😊

[@ananyaarya2465]

I was able to do this question without even watching the video!! thankyou so much sir

[@Pepcoding]

Bhot he bdiya beta, aise he lge rho aur aage bdte rho.

[@kunalnayak2121]

best, amazing, fantastic, fantabulous, extraordinary, excellent, over whelming !!! Aur bhi likhta but aur words dimaag me nhi aare.

[@Pepcoding]

wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.

[@ShMayank]

Hands down the best explanation online.

[@Pepcoding]

Glad you think so!

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.

[@alokesh985]

Sir, truly, you are at a different level... Amazing... The way you taught this, I will never forget this problem

[@namansinghal6054]

No words to express how great and valuable this content is. 🤩

[@Pepcoding]

wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.

[@playwithpinkman1570]

Tackling DP Questions should start from generating a recursive statement and using memoization (Bottom up Approach) I personally believe tabular can be understood very well after that and why we did what we did

[@Pepcoding]

Beta recursion pr aache khase questions kre h hmne, uske baad I think ki har bache kisi bhi question ka memoization vala solution khud se kr he payega to memoization vala solution apke liye homework h aur agr sb kuch main he krva dunga to bache apna dimaag kaise chlayege. To jo krva diya ya jo similar part h vo apka homework aur muskhil vala part, main cover kr he deta hu video main.

[@rakeshbaghel9126]

sir app bhut accha samjhate h , 2 3 4 year me jo college student h unke liye koi programm laiye ,sir app c++ me padhate to bhut accha rhta, hme competative programming me edge milta jyada

[@nitishnegi2449]

Your explanation is god level

[@deepaksrivastava7434]

Sir, your videos are a blessing for quick and deep understanding. But you raised the stakes really high : Nagarro!

[@prabhatkashyap8333]

kya sahi tarikhe se samjhaya h bhai, i am watching your video for the first time, and i really liked the way how you try to make it simple.

[@Pepcoding]

Thank you so much 😀

[@ashwinvarma9349]

Sir, please explain the dp solutions with recursion as well🙏

[@MegaArvind111]

static void printCoinCombination(int[] arr, int idx, int sum, String numSet, int target) { if (idx == arr.length && sum != target) { return; } if (sum == target) { System.out.println(numSet); return; } if (sum > target) { return; } if (idx < arr.length) { printCoinCombination(arr, idx, sum + arr[idx], numSet + " " + arr[idx] + " ", target); // Self repeating call printCoinCombination(arr, idx + 1, sum + arr[idx], numSet + " " + arr[idx] + " ", target); // Yes option direction in Euler printCoinCombination(arr, idx + 1, sum, numSet + " " + " ", target); // No option direction in Euler } }

[@Harsh-Choudhary451]

No words to describe Sumeet sir He is really genius

[@prachi_s_h]

thank you soo much from ❤.. I'm here just for telling that I was able to solve this que without watching solution vdo.

[@yelp9359]

Sir kya hm isko v 2D dp array use kr k solve kr sakte hai jaise hmne target sum subset ko solve kiye tha? Waha pe hm req - curr sum ko find krte the , pr yaha pe infinite coins hai to target sum ko current se divide kr k remainder ko Search krenge ?

[@pankhuri4u]

Amazing explanation. So clear and detailed !! Thanks Sir for always going an extra mile to explain.

[@Pepcoding]

Glad it was helpful! Keep learning. And for better experience and well organised content visit nados.pepcoding.com

[@prakharshreshtha375]

Explanation is great. However I am confused as the solution returns the total no of combinations, but the title says minimum number of coins.

[@karanveersingh5535]

Yeah u are right

[@ananyaagrawal4364]

Sir I am not able to recognize when to use 2D array when not? please tell me some path sir

[@mohammadkaif8143]

When repetetion is allowed, then use 1 D else 2D

[@Bdixit]

I think before tarvelling and solving for arr[i] one coin, we must check if arr[i] one coin is less than the total amount we need to form, else we may go out of bound in dp array.

[@nomadshubham3907]

Definitely 👍

[@kaushikanubhav9724]

If arr[i] is greater than the amount given, the loop won't run for that i. So I think everything is fine.

[@harshtekriwal131]

Sir I think in the input , there is coin of 0 , which I think is not valid , as we can use infinite number of coins of 0 to get a sum of 0. coins of 0 denomination should not be valid

[@tanishagupta5668]

for the case 1,2,5 as array and target as 11 this solution gives 11 as answer but the correct answer is 3, we need to solve that edge case by taking the min at every iteration

[@Pepcoding]

post your doubts on nados.pepcoding.com, community will help you out there.

[@punitpawar1]

@@Pepcoding Any idea how this can be modified for the above case - 1,2,5 as array and target as 11 this solution gives 11 as answer but the correct answer is 3

[@sudhanshusharma9123]

Thank you for a very good approach for this problem sir. I tried to solve this question using target subset sum approach but 2 test cases didn't pass. According to me it happened because the coins array also contains zeroes.

[@Pepcoding]

yes, it has zeroes

[@sudhanshusharma9123]

@@Pepcoding Thank you sir, now I have 2 separate approaches to solve this and hence a clearer understanding of the question

[@shashankjain6774]

sir this is not leetcode 322 problem as you have mentioned in the next video that it is leetcode 322

[@smitrami1757]

Sir please also discuss the time complexity of these algorithms. Great Content BTW !! :)

[@Pepcoding]

Noted

[@vithleshkumargupta]

Excellent Explanation 😊

[@puccaepisodes1509]

This video really helped me. Thank you!

[@rachit1650]

Best explanation over the KZbin

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@rachit1650]

@@Pepcoding sure sir

[@jameysiddiqui6910]

thanks for your effort for making these videos with detailed explanation.

[@Pepcoding]

Thankyou! I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms)

[@gemmember7495]

Thanks a lot for making this video, especially in for hindi explanation

[@Pepcoding]

for better experience why don't you use this same content on nados.pepcoding.com?

[@abhineetsingh6720]

this guy is a legend

[@priyanshgaurav4440]

sir in target sum problem we were not allowed to repeat a number to get to a target, in coin change we have inifinite supply and hence can repeat numbers aka coins to reach a target. Can you do a version of this question where we have 2 coins of each type, i.e. repition is allowed one time for each coin/value to reach the target. E.g. 3,3,2 is valid to reach 7 but 2,2,2,1 is not coz 2 has been used more than twice. I solved the question using the recursion levels and options method of the target sum question and adding an extra coin of each type in the array, i.e. instead of using the given [2,3,5] as the array of values, i made it [2,2,3,3,5,5] & applied target sum. Is there another approach possible?

[@nikitakushwaha9572]

Sir we don't understand 21,22 line . Plz code dry run one time. If i= 4 then condition should be fail (dp[j]+ =dp [3] ) .but condition not feiled.

[@kartickdhali4352]

Best explanation ❤️

[@garvitarora7777]

very nice video sir

[@abhirajchatterjee]

I was wondering why there is always 1 way fill solve 0th position that is the . while the other positions incrementally increase in value as the other numbers iterate over them, i.e. we get .22 , .223 , .233 but we do not get ....222 because if we think then we also always have 0 coins, so we can use that to pay also, but we keep it constant, after thinking for a while I realized that this is like the base case in a recursion where we always return a single value and do not make recursive calls.

[@sahilmalkania2533]

massive respect sir

[@fashionvella730]

i was solving it with the target sum technique technique worked

[@Nik-co4ew]

Best explanation Sir🙏 Thanx for the gr8 content that you provide.

[@Pepcoding]

Thank you so much and If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well Something like this Sumeet Malik from Pepcoding is making all his content freely available to the community You can check it out here - www.pepcoding.com/resources / Also, this is the youtube channel - kzbin.infoplaylists?view_as=subscriber

[@Nik-co4ew]

@@Pepcoding Sure Sir.

[@yygysgtyfugunvt]

sir hum kb 2d dp array use krenge aur kb 1d??....aur sir iss ques ko 2d se v kr sakte?? plzz sir reply

[@YashKumar-mo7dv]

Sir, when will you solve dp problems using memoization.... Please tell, i am facing lot of problems in tabulation

[@cosmicwhisperss]

Really great explanation I am just at 8min and have got it.

[@Pepcoding]

Thankyou beta! I am glad you liked it. I also hope that you are watching till end. Will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms)

[@cautioni]

isn't the title misleading? we're not finding min. number of coins, we're finding in how many ways can we have the target sum.

[@manasdeora4601]

It is. For minimum number, u have to do following public static int coinChange(int[] coins, int amount) { Arrays.sort(coins); int dp[] = new int[amount + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 0; i < coins.length; i++) { int currCoin = coins[i]; for (int j = currCoin; j < dp.length; j++) { if (dp[j - currCoin] != -Integer.MAX_VALUE) { dp[j] = Math.min(dp[j], dp[j - currCoin] + 1); } } } return dp[dp.length - 1] == Integer.MAX_VALUE ? -1 : dp[dp.length - 1]; }

[@ayanpaulnit]

Need to edit the title of this video a bit. This doesn't calculate the minimum number of coins required for a particular sum. I got confused in that but could use the explanation to tweak it to get the minimum number of coins required.

[@abhishek__anand__]

Great Video

[@aviralkhanduja5834]

sir agr hum memoization approach se kare toh sir isme 2d array lena padega na ,only a yes or no sir please won't take long but would really help me to check that i am on right track.

[@Pepcoding]

No

[@animeshkumarchoudhary6324]

I was able to code the soln just after watching five mins of the video

[@fv5895]

absoultely amazing.

[@Pepcoding]

Glad you think so!

[@aviralkhanduja5834]

Sir isme ye cheez constraint hai na ki denominations should be in inc order

[@prahladrana6391]

sir please kya aap ek video concepts of tabulation and memoization and their difference pr bana sakte hain ?

[@Pepcoding]

han beta. mai sari dp memoization se bhi karunga.

[@prahladrana6391]

@@Pepcoding thank you sir

[@ranavij]

THANKS SIR FOR THE GREAT EXPLANATION!!! KINDLY COVER Princess FARIDA DP QUESTION IN YOUR SERIES ,IT WOULD BE OF GREAT HELP

[@wecan2729]

College name?

[@ranavij]

gehu

[@wecan2729]

@@ranavij gehu?

[@wecan2729]

@@ranavij Graphic Era Hill University

[@ranavij]

@@wecan2729yes

[@ritwiksingh7589]

sumit sir when interview prep videos are going to be uploaded? are these videos uploaded under interview prep

[@anjneykumarsingh4461]

Bhai foundation toh kro

[@Pepcoding]

Nhi beta, ye foundation he hai. Interview prep start hone ko hai.

[@anjneykumarsingh4461]

Sir foundation pura krdijiyega strings dp

[@ghanendrapanwar165]

Sir in this series of of five questions (of dp taregt subset) do we have any trick to know when we will use 2d dp and when 1d dp..

[@vivekgaur7281]

did you know ans to your query now ?? if yes plz enlighten me too i have same doubt

[@ms_anirudh]

FANTASTIC !!!

[@rupalirajput2411]

Sir, for interview we have to prepare for Dynamic programming for both top-down and bottom-up or bottom-up is enough.

[@Pepcoding]

beta, agar concept clear hai to ek he kaafi hai

[@rupalirajput2411]

@@Pepcoding ok sir thanku

[@anjneykumarsingh4461]

Agr sir k student ho toh minimum 3-5 approach of solution dene chaiye

[@Curio_Amit]

Sir pta kaise chalega ki dp ein 1d array ke ya 2d array

[@Curio_Amit]

Sir pta kaise chalega ki DP mein 1D array le ya 2D array?

[@ztrixx3280]

it may be a naive question, but why we didn't use a 2d array here??

[@alokesh985]

Why would you want to use a 2d array when a 1d array is making so much sense, and is also easier to code

[@kkiitian]

it some how doesnt click to me that combination of paying 0 is 1. I feel that it should be 0. there is no combination.

[@shwetagupta8721]

SIr mujhe DP samjh kar nahi aa raha h , matlab I've tried watching your videos ,concept b samjh aa raha h par maza sa nahi aa raha h jaise aur topics me aata h. Kya karu sir? dp se to phobia type ka bann raha h 😣😣😣

[@jatinkumar4410]

Very nicely explained...

[@Pepcoding]

Thankyou beta! I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc

[@jatinkumar4410]

@@Pepcoding sure sir

[@kaushalsharma9777]

Sir if we had the constraint of single use , tb Kya change krte?

[@Pepcoding]

beta ise 2d bna deta. Firr ye question target sum subset jaisa ho jata

[@AshishGusain17]

thanks

[@jatinlodhi980]

sir combination ke value bhi print karni hoti to?

[@rishabgangwar950]

This is what people mean when they say there is a ton of free material available which is better than any paid content.

[@prabhatkashyap8333]

can you tell me one thing, ki hame pata kaise lgta h ki dp 2d array banaega ya 1d?

[@Pepcoding]

beta isse 2 video next wo discuss kia hai jab coin change aur target sum ko sath analyse kia hai

[@rohanraonallani561]

Sir,kya trie ds bhi is course key part hai

[@Pepcoding]

hanji. Trie will also come asap.

[@yoyo8293]

sir agar count with all combinations (223,25 etc) requirement hota toh kya karte?

[@Pepcoding]

video already dali hui hai

[@mukultaneja8014]

Hello sir, The meaning which I assigned to the box is - If I am on box 5, I would say it contains the ways I can give 7 rupees using those denominations. So the small problem becomes if I have 7 rupees, How I can pay 7 rupees and large problem becomes, if I have 0 rupees How I can pay 7 rupees? Is this approach alright?

[@Pepcoding]

hotch potch hai. dobara padho comment. Meaning clear nahi hai. Dobara express karo.

[@mukultaneja8014]

@@Pepcoding Meaning of the box with index 5 - Agar mere paas 5 rupee hai then mere paas kitne ways hai ki Mai 7(target) rupee pay Kar sakta hu denominations(2,3,5) ko use karke. Aapne source target amount rakha and destination zero and I did opposite.

[@Pepcoding]

han sahi hai

[@universeboss4865]

Sir, I have a doubt my code is running fine, but in the case of 0 rupee coin it's giving wrong answer. What to do...??

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@shubhammittal4389]

best dp videos

[@Pepcoding]

Glad you think so! For better experience and well organised content sign up on nados.io and start learning.

[@utkarshsharma6650]

I did your question through your approach on GFG but test case is not passing 149 11 1 2 3 4 5 6 7 8 9 10 11 output is: 259819164 long long minimumNumberOfCoins(int coins[],int numberOfCoins,int value) { int dp[value+1]; for(int j=1; j

[@Pepcoding]

Beta, koi edge case miss ho rh hoga. Will check and correct it, if there will be any problem.

[@sachinduhan3022]

how can somebody dislike this video?

[@universeboss4865]

Sir, dp array 1D bnau ya 2D bnau ye clear nhi ho rha. Sir, plz aap mera ye doubt clear kr dijiye...

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@universeboss4865]

@@Pepcoding okay sir no problem...

[@RishabhJain-uv7zj]

Is it necessary for the coin array to be sorted then?

[@priyansh88]

According to him Yes!. Anyway, sorting it beforehand will not affect the time complexity.

[@anubhavgupta4412]

no array need not to be sorted

[@priyansh88]

@@anubhavgupta4412 true

[@RahulGupta-vg2qi]

Sir coins array to sorted hona jaruri hein?

[@Pepcoding]

bilkul nahi. index ke hisaab se to hmesha sorted hota hai

[@ankoor]

Python3: O(nm) Space: def coinCombinations(A, S): n = len(A) T = [[0 for _ in range(S + 1)] for _ in range(n + 1)] for i in range(n + 1): for j in range(S + 1): if i == 0 and j == 0: T[i][j] = 1 elif i == 0: T[i][j] = 0 elif j == 0: T[i][j] = 1 else: col = j - A[i-1] T[i][j] = T[i-1][j] + (T[i][col] if col >= 0 else 0) return T[n][S] S = 7 A = [2, 3, 5] print(f"Number of combinations of {A} that make {S}: {coinCombinations(A, S)}")

[@jaygujarathi7296]

Sie when to use 2D dp and 1D dp?

[@vivekgaur7281]

did you know ans to your query now ?? if yes plz enlighten me too i have same doubt

[@nikitakushwaha9572]

Sir combination kaise ban rha vo confirm h but code me kaise Cal rha h isme confusion h .

[@Pepcoding]

For better experience and well organised content sign up on nados.io And for being updated follow us on Instagram instagram.com/pepcoding/

[@deveshkumar6533]

sir plz fix the faulty test case.... where denomination value is 0

[@Pepcoding]

hanji, isko fix karna jaroori hai

[@VinayKumar-vm1hg]

Sir question dp ka h ya nhi pata kaise krenge

[@Pepcoding]

recursion tree bnaie. Agar same question dobara dikhe to samajh jaie ki DP hai. yahan se shuru kijie www.pepcoding.com/resources/online-java-foundation/dynamic-programming-and-greedy/fibonacci-dp-official/ojquestion

[@rajdeepghosh5556]

11 with 1,2,5 me nhi chal rha hai ye...leetcode me.

[@fashionvella730]

i was trying to solve with the very same tehnique but was not getting point

[@pinakeekaushik7803]

sir isi question ko memoization and recursion se kaise kare? Thank you sir.

[@Pepcoding]

Beta, uski videos alag se bnaunga

[@deeptarkoroy6724]

class Solution { public: int solve(vector&coins,int amount,int n,vector&dp) { if(n

[@harshita2429]

Amount array me amount +1 ku liya h

[@creativegiant148]

Recursion se karte hain toh dimagh lagana hii nahi padhta par iteration meh bahut dimagh lagana padhta hai

[@Pepcoding]

Recursion main expectation aur faith assume kr k kaam chl jata h na to itna dimaag nh lgana pdta.

[@sumaiyasafdar6845]

Why did we print dp[amt] and not amt+1 please help

[@universeboss4865]

Bcz we pass index inside subscript of array not it's size which is one greater than the index

[@HimanshuSingh-ob9qo]

👌

[@Pepcoding]

Keep learning, Keep growing and keep loving Pepcoding!😊

[@sagar5430]

Yadhi yee Playlist hard lag rhi hai yaa smajh nahi aa rhi toh bhaiyo pepcoding ke rajnesh sir ki dp Playlist dekhlo 28 videos hai small si

[@sagar5430]

And see the result

[@kshitijnath]

Sir 2d array se nahi kar payenge?

[@Pepcoding]

jab 1d se ho rha hai to 2d kyun karein? ek video hai jo target sum subset, permutations aur combinations ko compare karti hai. iske ek do question baad hai. usko dekho

[@universeboss4865]

@@Pepcoding haa sir but 2d dp array use krta hu to ek test case fail kr jata h mere answer aate h 69 or expected output h 276.

[@mansijoshi7227]

When he corrected bhaiya to behen xD

[@LegitGamer2345]

whats the time complexity ?

[@Pepcoding]

N square

[@LegitGamer2345]

@@Pepcoding thanks sir !

[@ShootOniPhone914]

Great explanation sir very perfect 🔥🔥🔥

[@Pepcoding]

Keep learning. And for better experience, visit nados.io, where you will get well curated content and career opportunities.

[@abhishekinamdar2784]

wornderful technique and explaination. The worst case complexity will be n^2 if coins will range from 1 to n and sum = n. correct me if I'm woring.