I love the fact that you solved the problem likes some one attempting it for the first time and showed the error one might run into. That made it intuitive to follow. Please keep making these!
+1 on this. My code is EXACT same as the one at ~5min and I've been wondering why I'm unable to get the right solution. Awesome job for guiding us through all the way!
Love the way you teach from a general solution that might end up in some exception to a perfect solution checking all possibilities, even I did the mistake of repeating combination but cleared after your watching your video. Please add up more videos regarding Dynamic problems and Greedy problems.
Hi! The code explanation is super clear. Is it possible to explain how we can get the sets of possible combinations (not only that a combination exists, but the real numbers in the set)?
I think the second solution has an issue of iteration. the 'coin' in the loop is adding up as the index which should be loop thorough as the elements in the coins array. Since your coins array is [1, 2] which match the index, the solution will work, but if your coins array is [1, 2, 5] the solution will fail!
Thanks for a great video. I did an alternative implementation in Scala without any assignment/for loop to make it even more functional-style. The proposed solution in the video might be more efficient though since I haven't figured out if it is possible to make this approach tail recursive somehow. (click on the show more link to see code) def countChange(money: Int, coins: List[Int]): Int = if (money < 0) 0 else if (money == 0) 1 else coins match { case Nil => 0 case head :: tail => countChange(money - head, coins) + countChange(money, tail) }
In your recursive solution that didn't take into account a current coin, why did your recursive solution 3 - 2 = 1 iterate back to 1 - 1 again?isn't that outside the for loop?
lol recurrence relations are not fun! recurrence relations are difficult enough with one parameter [but...T(0,m)= c1, T( 1 sounds like a terrible start haha]
Hi Neil, Thank you for the amazing explanation! I had a question though. How do we attempt the same with memoization? I tried with *memoization* and it returns *all the combinations with permutations* instead of just the unique combinations. Here's my code if you or anybody could help me find any error: function coinChange(denominations, value, coin, memo=[]){ if (memo[value]) return memo[value]; if (value < 0) return 0; if (value === 0) { return 1; } let amount = 0; for (let x = coin; x < denominations.length; x++) { amount += coinChange(denominations, value-denominations[x], x, memo) } return memo[value] = amount; } coinChange([1, 5, 10, 25], 6, 0) //returns 3 instead of 2
print combo along with number of combo... coins = [1,2,3] temp = [] def combo(amount, current_coin, temp): if amount == 0: print("change is 0 ", temp) return 1 if amount < 0: return 0 nCombos = 0 for i in range(current_coin, len(coins)): temp.append(coins[i]) nCombos += combo(amount-coins[i], i, temp) temp.pop() return nCombos print("number of combos : ", combo(4, 0, temp))
Nice explanation, but this method won't work when one of the coin denominations is not a multiple of another. In this case, "1" is always among the coins and hence every coin denomination is a multiple of it.
This solution assumes the coins are arranged in a sorted array. If the coins were {2,1} your solution would fail. So you have to sort the array before applying the recursion.
This is not the correct way of looking at this problem, you are introducing cycles in the problem, whereas Dynamic Programming has to be a topological sorting of a DAG ..
I love the fact that you solved the problem likes some one attempting it for the first time and showed the error one might run into. That made it intuitive to follow. Please keep making these!
+1 on this. My code is EXACT same as the one at ~5min and I've been wondering why I'm unable to get the right solution. Awesome job for guiding us through all the way!
I found the opposite.
I like the way you describe how to count permutations and combinations each. Very helpful
This is the best explanation to the Coin Exchange problem, better than Gayle's explanation. I like the simple way you drove the solution
Really loved the solution, especially how you made some mistakes at first purposely and then solved them. You rock \m/
this video is a lot easier to understand than your another one(dynamic programming approach). thanks bro
Loved the initial code vs final code explaination. I was hitting the exact same issue. Very helpful indeed
I ran into same error when i tried to solve the problem. Keep making more of these. Thanks
The way you described the problem was very thorough! Keep up the good work!
how would we print out all the combinations?
Simply brilliant ! I was solving the DavisStaircase using the first part of the video. Thanks a lot !!
superb explanation . you don't just explain but you make me to realize the mistakes,...... :)
Love the way you teach from a general solution that might end up in some exception to a perfect solution checking all possibilities, even I did the mistake of repeating combination but cleared after your watching your video.
Please add up more videos regarding Dynamic problems and Greedy problems.
Great solution! Please note this problem is different than LC 322. Coin Change (minimum # of coins for an amount)
Wow Wow Wow. You deserve more subscribers.
Why memorization not working in this Code?😟😦😦😦😦😦😦😦😟😦😦😟😟😟😟😦
liked that whiteboard helped out a lot.
I was attempting it in the same way,but got stuck when i had to remove the permutations.. and u helped me.. Thanks alot!!
Same here.
Hi! The code explanation is super clear. Is it possible to explain how we can get the sets of possible combinations (not only that a combination exists, but the real numbers in the set)?
intuitive explanation!
Thanks.
How would we print out all the combinations?
Wow youre really patient, nice!
thanks for taking the time to explain this. nicely done.
This helped me a lot, thanks.
Why do we need the static value amount if we're not going to use it?
I think the second solution has an issue of iteration. the 'coin' in the loop is adding up as the index which should be loop thorough as the elements in the coins array. Since your coins array is [1, 2] which match the index, the solution will work, but if your coins array is [1, 2, 5] the solution will fail!
Thanks for a great video. I did an alternative implementation in Scala without any assignment/for loop to make it even more functional-style. The proposed solution in the video might be more efficient though since I haven't figured out if it is possible to make this approach tail recursive somehow. (click on the show more link to see code)
def countChange(money: Int, coins: List[Int]): Int =
if (money < 0) 0
else if (money == 0) 1
else coins match {
case Nil => 0
case head :: tail => countChange(money - head, coins) + countChange(money, tail)
}
Great Explanation! Loved it
excellent explanation
In your recursive solution that didn't take into account a current coin, why did your recursive solution 3 - 2 = 1 iterate back to 1 - 1 again?isn't that outside the for loop?
this is very smooth
How would you print the combinations along with the total no of combinations?
thank you for the clear explanation, really helpful
How to actually print out all combinations of amount? Let us say for amount=4, coins=[1,2,3] need to print out: (1,1,1,1); (2,2); (1,1,2);(1,3)
i loved the way it is explained. Simple and easy to follow. What is the time complexity of this solution?
lol recurrence relations are not fun! recurrence relations are difficult enough with one parameter [but...T(0,m)= c1, T( 1 sounds like a terrible start haha]
What's the time complexity for this program??
how about calculating time and space complexity
nice explanation!
Hi Neil,
Thank you for the amazing explanation! I had a question though. How do we attempt the same with memoization? I tried with *memoization* and it returns *all the combinations with permutations* instead of just the unique combinations.
Here's my code if you or anybody could help me find any error:
function coinChange(denominations, value, coin, memo=[]){
if (memo[value]) return memo[value];
if (value < 0) return 0;
if (value === 0) {
return 1;
}
let amount = 0;
for (let x = coin; x < denominations.length; x++) {
amount += coinChange(denominations, value-denominations[x], x, memo)
}
return memo[value] = amount;
}
coinChange([1, 5, 10, 25], 6, 0) //returns 3 instead of 2
Thank you very much!! Great explanation!!!
Fantastic explanation...
Great way of explaining
should we use a memo?
What is the time of this code, O()?
You're amazing
Grea videot! Keep it up!
That would be great if you add memoization to it aswell. you need to save: Mem[(money,index)] into your table
so helpful!
print combo along with number of combo...
coins = [1,2,3]
temp = []
def combo(amount, current_coin, temp):
if amount == 0:
print("change is 0 ", temp)
return 1
if amount < 0:
return 0
nCombos = 0
for i in range(current_coin, len(coins)):
temp.append(coins[i])
nCombos += combo(amount-coins[i], i, temp)
temp.pop()
return nCombos
print("number of combos : ", combo(4, 0, temp))
very helpful !
Nice explanation, but this method won't work when one of the coin denominations is not a multiple of another.
In this case, "1" is always among the coins and hence every coin denomination is a multiple of it.
very nice work
This solution assumes the coins are arranged in a sorted array. If the coins were {2,1} your solution would fail. So you have to sort the array before applying the recursion.
I don't think this is correct. Try coins = [2, 5, 3, 6], amount = 10. Should be 5 but it gives 7 (has duplicates).
The above method only works if the coins are sorted. He didn't mention that
Excellent
This will fail for test case :
sum=4
coins = {1 2 3}
it should print 4, i.e
{1,1,1,1}
{1,1,2}
{2,2}
{1,3}
your solution shows 7
i am too stupid!! can't formulate a recursion problem on my own. fml :(
Hey man, recursion is a tough concept to master and everyone struggles to become confident in creating recursion solutions. Just keep at it!
This is not the correct way of looking at this problem, you are introducing cycles in the problem, whereas Dynamic Programming has to be a topological sorting of a DAG ..
wrong answer.. the algorithm is wrong...
i already tried in oj