7 Subset Sum Problem

  Рет қаралды 593,700

Aditya Verma

Aditya Verma

Күн бұрын

Пікірлер: 785
@keeratsachdeva5359
@keeratsachdeva5359 4 жыл бұрын
Sir just for confirmation - 20:58 me t [ i - 1 ] hona chahiye na(Because we have processed the last element)?
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
Yes yes of course, thats just a typo !! Wait here let me pin your comment to help others !!
@keeratsachdeva5359
@keeratsachdeva5359 4 жыл бұрын
This playlist is really helpful.Thanks Sir.
@nirmitsrivastava
@nirmitsrivastava 4 жыл бұрын
@@TheAdityaVerma Hey, You can add correction in the video as a popup. Great Work Anyways.
@manishrawat6678
@manishrawat6678 4 жыл бұрын
@@harshitanand8216 i will always start from 1 since we already did the initialization for i = 0
@vivekojha4807
@vivekojha4807 4 жыл бұрын
Thanks Keerat! Wohi soch raha tha
@PrashantSedhainOfficial
@PrashantSedhainOfficial 3 жыл бұрын
Watched all the ads just to support you! I usually have ad blocker. You are killing it!
@TheAdityaVerma
@TheAdityaVerma 3 жыл бұрын
Purushhottam Prashant hai bhai tu 🙏 jokes asides, Thanks a lot brother, this world really don't have many people like you :D 🙏
@aakashgarg8352
@aakashgarg8352 3 жыл бұрын
@@TheAdityaVerma 🤣🤣🤣🤣🤣🤣
@PrashantSedhainOfficial
@PrashantSedhainOfficial 2 жыл бұрын
@Saswat Pattnaik uBlock Origin Chrome Extension.
@ScienceSeekho
@ScienceSeekho 2 жыл бұрын
Better buy a youtube premium
@ishwarshelke128
@ishwarshelke128 2 жыл бұрын
​@@ScienceSeekho better use another browser where there are no ads for any type of content
@savithalakshmanan2842
@savithalakshmanan2842 4 жыл бұрын
Mind blowing explanation, I usually do not comment but this sort of material needs a big applaud.
@raunop8208
@raunop8208 2 жыл бұрын
if you got placed now,please refer me
@chatpapdi8225
@chatpapdi8225 2 жыл бұрын
@@raunop8208 koi ni hota refere bhai padhleeee
@chatpapdi8225
@chatpapdi8225 2 жыл бұрын
@@raunop8208 experience se bata raha hu
@riteshMusk
@riteshMusk 4 ай бұрын
@@raunop8208 She in Microsoft bro
@0anant0
@0anant0 4 жыл бұрын
7 of 50 (14%) done! Very nice explanation of initialization and the summary at the end was a great wrap-up, tying everything together.
@bodlahruthik5730
@bodlahruthik5730 4 жыл бұрын
I"ve done course from coding ninjas but this playlist makes me understand dp easily , serioulsy you are an inspiration
@anuragjana111
@anuragjana111 3 жыл бұрын
Thanks for the advice.Gonna complete dp from here and then go back to that course.
@basharatsaigal9800
@basharatsaigal9800 3 жыл бұрын
One day your juniors of NIT Bhopal will be proud to have a senior who could teach programming concepts in such a beautiful way! Keep going, love the content.
@PalakMittal
@PalakMittal 3 жыл бұрын
But I think he is from MNNIIT Alahabad
@ananypandey1310
@ananypandey1310 2 жыл бұрын
@@PalakMittal NIT ; )
@PalakMittal
@PalakMittal 2 жыл бұрын
@@ananypandey1310 Yeh! My bad 😅
@suryanshuverma6908
@suryanshuverma6908 2 жыл бұрын
@@PalakMittal No, he is from MANIT Bhopal
@siddhartharora1597
@siddhartharora1597 4 жыл бұрын
Great work brother, u are like the interviewbit of teaching , u have the crux of everything and complete understanding of what u r teaching!!. Hats Off..
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
So nice of you !! Thanks was really a creative compliment 😂✌️
@ramupadhya8155
@ramupadhya8155 4 жыл бұрын
@@TheAdityaVerma link g4g you attached is slightly different , aint it ?
@shubham277
@shubham277 4 жыл бұрын
bhai agr teri videos aj se 1 month phle mil jati dp ki too life set ho jati. Very good job dude. I think tushar roy should learn something from you.
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
Thanks a lot brother, Please share the content so the same doesn't happens to others and these videos get to them in time before interviews.
@starc701
@starc701 4 жыл бұрын
bhai tushar roy ke video tab k hai jab .....koi itne video nhi hua krte the...isliye usko pta nhi hai ki viewers kya chahte hai..
@teetanrobotics5363
@teetanrobotics5363 4 жыл бұрын
Best channel on youtube . On my way to finish the dp playlist
@harshavardhankanoj6021
@harshavardhankanoj6021 2 жыл бұрын
To pass all corner cases, we should correct "if statement". Runnable code: Python code, dp=[[0 for j in range(sum+1)]for i in range(n+1)] for i in range(n+1): for j in range(sum+1): if j>0 and i==0: #corrected line j should be greater than 0, j>0. dp[i][sum]==False elif j==0: dp[i][j]=True elif arr[i-1]
@chandakaBalaji
@chandakaBalaji Жыл бұрын
my code failed exactly in that case and im glad that someone mentioned like u mentioned the corrected one
@tanmaymalhotra4450
@tanmaymalhotra4450 3 жыл бұрын
Your videos helped me a lot to grasp the concept of DP . Cannot thank you enough for this precious content that you make. Keep teaching brother .
@MohitKumar-sd3ld
@MohitKumar-sd3ld 3 жыл бұрын
So many institutes will fail to explain like this. Hats off to you
@lokeshgoyal9419
@lokeshgoyal9419 Жыл бұрын
Note to myself : We have to decrease the number of elements by 1 in both Inclusion and exclusion! Inclusion means, we take current element and start to identify the possible solutions for the remaining sum with rest of the elements! Exclusion means, we discard the current element and start to identify the possible solutions for the same sum with rest of the elements excluding the current one!
@gamerhu7462
@gamerhu7462 3 жыл бұрын
this guy is just GOD OF DP!!!! prev video dekha n problem explanation se hi khud se recursive and top down bna liya! I wish hmare teacher aisa pdha pate!!!!!!
@mridulgoyal3430
@mridulgoyal3430 4 жыл бұрын
This is genuinely the GOD level explanation !! Thanks Bro
@amitkumarsingh5414
@amitkumarsingh5414 4 жыл бұрын
Soon your playlist will come in the top 10 , best wishes. I just want you to add more videos on Algorithm :)
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
Thanks brother !! Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@a.yashwanth
@a.yashwanth 4 жыл бұрын
@@TheAdityaVerma How is your job going. You mentioned in previous video that you got 16L package.
@SuperSuneel
@SuperSuneel 4 жыл бұрын
Friends explanation for quick exam prep....remembering all friends who are just bright and sharp as you who would help a friend in need....Superb explanation.....never fell asleep even if your video is long. The power of your explanation is superb....keep it up. hope to see more from you a lot more!!!
@kajalmishra7367
@kajalmishra7367 4 жыл бұрын
You are awesome man! I never had imagined that I will be able to solve DP problems but I can now, all thanks to you. Keep on this amazing work :)
@arch3994
@arch3994 2 жыл бұрын
speak sach only People from your family go to Vaishnodevi and cry in a bhawan while chanting Mata bhajan and when you and your family come back to hometown you people start doing fraud and do dhokhebaazi in business and eat money of poor people Do remember mata is watching everything your crocodile tears in bhawan vaishno Devi and your bad deeds in your business and in some other place
@_aka5h
@_aka5h 2 жыл бұрын
@@arch3994 wtf
@rishabhinc2936
@rishabhinc2936 Жыл бұрын
@@arch3994 lmao
@rohitchatterjee5298
@rohitchatterjee5298 4 жыл бұрын
Best teacher ever... Thanku for helping all of us..
@akshitmittal1251
@akshitmittal1251 10 ай бұрын
great work brother. Kahi ni mili esi understanding, jitni teri basic videos se mil gayi. Thanks
@riteshpuj9566
@riteshpuj9566 2 жыл бұрын
I just blindly followed your logic and method to convert the recursive code to tabulation version and it worked without even testing it manually. I had automated tests written to verify. Thanks for sharing your knowledge 🙏🏽
@accepted5856
@accepted5856 4 жыл бұрын
The best video ever on dp..The way you are teaching....Is just amazing
@asthamishra287
@asthamishra287 7 ай бұрын
Really very helpful . I don't know how many times I have come back to re-watch this playlist.
@yashshukla1256
@yashshukla1256 4 жыл бұрын
Mast Padhaya Bhai Dil Khush ho gaya Dekh kar, Khud se ab problem solve kara to maja hi kuch aur tha concept mst clear kara bhai !!!
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
Thanks Brother !! Do share where ever you feel right to help the channel grow !!
@harshitasingh963
@harshitasingh963 3 жыл бұрын
Undoubtedly the best playlist on DP (I didn't go through the comment section and then re-watched previous videos to see if I missed a concept. LOL)
@sleepypanda7172
@sleepypanda7172 3 жыл бұрын
after watching his videos it feels like I can achieve Nirvana 😅. I get so much peace after understanding the concepts because he teaches so damn well!!
@yatri6329
@yatri6329 2 жыл бұрын
But it doesn't pass all the testcase
@Shourya_performs
@Shourya_performs 2 жыл бұрын
@@yatri6329 whats the problem? I might help
@punitsharma9703
@punitsharma9703 2 жыл бұрын
Solved my first DP question after watching your tutorials. Huge Thanks bro!
@Shourya_performs
@Shourya_performs 2 жыл бұрын
Kudos to u brother. I too hv solved my first Dp problem 2 days back.. I knw this feeling man.
@danushbasanaboyina1306
@danushbasanaboyina1306 5 ай бұрын
The best explanation in the youtube on DP where I found the explanation even in Matrix wise ,where no one does..
@ASHISHKUMAR-jh9kw
@ASHISHKUMAR-jh9kw 2 жыл бұрын
I was able to initialise dp array by using recursion. No one tells this thing is comming from recursion base condn. Great work man.
@mansigoyal3440
@mansigoyal3440 4 жыл бұрын
videos dekh kr apki mn krta hai bs dekhte hi jao....best person
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
ye to kuch kuch 5- start jese ho gya - "khao aur kho jao" 😂😂
@eyeamkd
@eyeamkd 2 жыл бұрын
I loved the way you explain and keep focusing on the details again and again to make it stick, but a dry run with any example would've been better.
@hiteshmitruka6419
@hiteshmitruka6419 3 жыл бұрын
Solved this without even seeing the video. Knapsack explanation🔥🔥🔥🔥
@sahil1053
@sahil1053 2 жыл бұрын
nobel prize
@satya_k
@satya_k 2 жыл бұрын
To understand why that "max" was changed into Boolean OR operation: Once you write the recursive solution, you will observe that when arr[n-1] is less than or equal to the subset sum, the subset sum can be found in the array (i.e. we return true) in either of the following cases: 1. a. If the (subset sum - arr[n-1]) can be found in the first n-1 elements of the array (Including arr[n-1] in subset) 1. b. If the subset sum can be found in first n-1 elements of the array (Not including arr[n-1] in the subset) So we return Boolean OR of the two above give conditions return subsetSum(arr, n-1, sum-arr[n-1]) || subsetSum(arr, n-1, sum))
@AbsolutePain
@AbsolutePain 2 жыл бұрын
Can you Post the recursive code solution ! Thanks
@satya_k
@satya_k 2 жыл бұрын
​@@AbsolutePainyeah, here you go: bool isSubsetSum(int arr[], int n, int sum){ if(n==0) return 0; if(sum == 0) return 1; if(arr[n-1]
@tusharjajodia9077
@tusharjajodia9077 3 жыл бұрын
Yaar!!!!. Ek he toh dil hai kitne baar jitoge.
@arunkranchi
@arunkranchi 4 жыл бұрын
If you do max as for Knapsack it will be same logically, as Max for two booleans is same as Max. 1 or 1 is same as Max(1,1), 1 or 0 is same as Max(1,0) and 0 or 0 is same as Max(0,0)
@musicfan1695
@musicfan1695 4 жыл бұрын
bhai tu meri zindagi ka pehla aur iklauta pyaar hai. Tere channel ko meri duaein lage. Lagni zaroori bhi hai, mai heejda hu
@PawanKumar-it7np
@PawanKumar-it7np Жыл бұрын
Bhaiya teacher ho to aapke jaisa !! Maza aa gya !! 😁
@sachinmagdum
@sachinmagdum Жыл бұрын
@TheAdityaVerma, I loved the way you put your thoughts. Great effort. This code allows to take each number multiple times. For input array {2, 5} and target sum=90 your code returns true. We should either change the problem statement to call it unbounded or fix the code to take each number only one time. One way to fix code is take t[i-1][j-arr[i-1]]. i.e. Corrected code: t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j]; Your code: t[i][j] = t[i][j-arr[i-1]] || t[i-1][j];
@SauravKumar-bp4jj
@SauravKumar-bp4jj 29 күн бұрын
At last found someone who noticed. Thank you for your answer. Can you explain how the corrected code works. I couldn't get it
@archanasingh3643
@archanasingh3643 4 жыл бұрын
Best video with so much ease...teaching style is awesome. I saw Tushar Roy's video for same problem. There is no comparison with this video. Accent and language doesn't make problems seem easy :)
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
Haha Thanks Archana !! I love his accent tho 😂😂😂😂I mean who doesn't right? 😅
@aanchalsharma5264
@aanchalsharma5264 4 жыл бұрын
@@TheAdityaVerma but you teach as a elder brother or a friend ...
@aanchalsharma5264
@aanchalsharma5264 4 жыл бұрын
@@TheAdityaVerma thank u How to select which term to take as row and column.... What if we take vice versa???
@sasirekhamsvl9504
@sasirekhamsvl9504 3 жыл бұрын
love your videos. If you did not made this playlist I might have never understood DP.
@aishwarya1895
@aishwarya1895 3 жыл бұрын
Literally thanks a lot from the bottom of my heart
@nikitajaiswal9112
@nikitajaiswal9112 2 жыл бұрын
I can't believe I am able to solve this problem by own 😊😊😍thank you😊 for clearing concepts and give a way to how to approach
@Rajmayank24
@Rajmayank24 2 жыл бұрын
In which language u code??
@rakeshrao2cool
@rakeshrao2cool 3 жыл бұрын
Aditya Verma, Nice explanation, If you could dry run your inputs and show the output right there, it will be a bit easier to understand
@AniketSinha291
@AniketSinha291 4 жыл бұрын
1 suggestion in Knapsack: When you are processing i-th element, you can create variable iterVal = val[i-1] and iterWeight = wt[i-1] and use these variables in the max expression. This will help in better understanding the concept as well as look less scary & more readable: max(iterVal + t[i-1][j - iterWeight] , ...)
@SourabhAnandJha
@SourabhAnandJha 3 жыл бұрын
sahi baat mere coder!!
@sahil1053
@sahil1053 2 жыл бұрын
nobel prize laya jae bhai k liye😪😐😐
@es_amit
@es_amit 9 ай бұрын
20:25 for changing max to OR, because if we found any subset of having sum == target then it means the main problem answer also is true so for making OR it will return true if we found any of the subset which having sum of target
@huntrz
@huntrz 2 жыл бұрын
Aditya, I am not exagerating. You truly deserve the Dronacharya award had they been giving it for academics.
@nitinchaurasia8910
@nitinchaurasia8910 4 жыл бұрын
@Aditya Verma how to print all the subset after we create the matrix....... ??
@HarshitGupta005
@HarshitGupta005 3 жыл бұрын
take a global list and fill that once you reach the answer
@karnatisaishashank1258
@karnatisaishashank1258 3 жыл бұрын
@@HarshitGupta005 how we can fill
@gauranshverma4364
@gauranshverma4364 4 жыл бұрын
You are doing a great job bhaiya....God bless you..
@fahadisrar2195
@fahadisrar2195 4 жыл бұрын
I am a GSOCian but my advanced CP isn't good enough...This is really helpful....Thanks a lot @Aditya Verma :)
@vaibhavgupta5776
@vaibhavgupta5776 4 жыл бұрын
bhaiya me sach me comment nahi karta zada par kasam se bhaiya yar bhut acha playlist banaya hai meko bhut kuch pata chala apki vedios seee me electronics ka student hu apne mere zindagi bana dii bhut achi vedio god blesss you
@ankitkumaryadav562
@ankitkumaryadav562 3 жыл бұрын
One of the Best tuturial>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
@sayleeshenoy5049
@sayleeshenoy5049 4 жыл бұрын
I saw many dp videos, so far this one is the best. Thanks for such great explanation. Keep posting such videos!
@sudhanshusharma9123
@sudhanshusharma9123 4 жыл бұрын
according to me, the memoization can not be performed normally in this question since there can only be 2 values in the memoized array i.e. true or false, so when initializing that memoized array with some value (such as initializing -1 in all cells of array in knapsack), we can not just initialize the array with either true or false since that does not ensure that whether the problem for that cell is solved before or not. Correct me if I am wrong.
@NishantSethigeek
@NishantSethigeek 2 жыл бұрын
Instead of appending True or false, you could append 1 or 0. Then before returning you could but a check and return accordingy. (Ik I am late :P)
@sudhanshusharma9123
@sudhanshusharma9123 2 жыл бұрын
@@NishantSethigeek Yes true, I think the initial value in that case can be -1, or if you are using java, can use Boolean class since the initial value it contains is null.
@sanghamitrahota1162
@sanghamitrahota1162 4 жыл бұрын
This was a really nice explanation. I was stuck in this from a day , couldnt relate. Thanks 😁 please keep making videos
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
Thanks !! I am glad it helped you !! Do share and subscribe.
@factoworld9527
@factoworld9527 Жыл бұрын
@@TheAdityaVerma bhai aap legend ho please video banao aur
@NehaGupta-zc3mo
@NehaGupta-zc3mo 3 жыл бұрын
I don't who & why people disliked the videos.. These videos & concepts are outstanding.. Aditya Verma u made DP easy for me :P Thanks alot for such content.
@sahil1053
@sahil1053 2 жыл бұрын
they don't like to understand things
@SohamDutta222
@SohamDutta222 10 ай бұрын
thank you for making this excellent video!! We all are grateful to you! Soon I will get a good job. Thanks to you!!
@DeepakSingh-sy4ws
@DeepakSingh-sy4ws 4 жыл бұрын
u r best bro.. i have learnt from many youtubers but you and traversay media are best .. ur basic is clear..
@gurpartapsingh1693
@gurpartapsingh1693 4 жыл бұрын
It would be really nice if you can dry one problem at the end of the video. Keep the good work going!
@sarthakagarwal221
@sarthakagarwal221 3 жыл бұрын
I tried to solve this problem without watching this video using recursion with memoization and it felt like a cake walk. Recursion has never been so easy to me. Thanks mate. I would like to buy a coffee for you. Do you have a patreaon link or something similar ?
@MALIWAL1000
@MALIWAL1000 3 жыл бұрын
Yes he has patreon now, check new videos for link.
@sarthakagarwal221
@sarthakagarwal221 3 жыл бұрын
@@MALIWAL1000 yes, already a member
@GauravKumar-lb6ze
@GauravKumar-lb6ze 3 жыл бұрын
have you got TLE with memoization?
@tanvivarshney6033
@tanvivarshney6033 3 жыл бұрын
I don't have words to thank you bhaiya, since itna accha to teachers rupee le kar bhi nhi pdhate jitni acchi education ap hmre lye de rhe ho, big thanks🤗
@ak67373
@ak67373 4 жыл бұрын
Bro please make videos on tree also ...🙏🏻🙏🏻it will be helpful for my interview....make all videos on trees
@testertest8571
@testertest8571 2 жыл бұрын
Completed 7 out 49 video....I will comment upto lecture 35 ., today on every video for sure..
@vaibhavm1007
@vaibhavm1007 4 жыл бұрын
Amazing playlist so far! The style of teaching the techniques rather than just the answer is awesome! Directly writing the bottom up solution feels tough though - when writing the code should we start with the recursive solution first and then convert it to bottom up as explained in prev videos?
@kirtikhohal3313
@kirtikhohal3313 2 жыл бұрын
Yes , i wrote the recursive function first , and then memoized it, and then I went on to write the actual iterative code
@akshanshsharma6025
@akshanshsharma6025 2 жыл бұрын
@@kirtikhohal3313 bool solve(int n,int sum,vector&arr) { if(n==-1 && sum==0)return true; else if(n==-1 && sum!=0)return false; else if(n!=-1 && sum==0)return true; else { if(arr[n]
@ayushkushwaha171
@ayushkushwaha171 Жыл бұрын
yes, I agree with this. Starting from a recursive solution seems more understandable and good in an interview.
@noobcoder8042
@noobcoder8042 2 жыл бұрын
I don't have any word to tell about your explaination technique b/c it is amazing keep it up bhaiya .The way you explain the question,i easily write the code without your seeing your code.
@ayushsingh3877
@ayushsingh3877 3 жыл бұрын
In description of this video , where u give example "Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True //There is a subset (4, 5) with sum 9", here , subset {3,4,2} is missing which also gives the sum 9. btw, your content is too op.
@utsavsharma4542
@utsavsharma4542 Жыл бұрын
This is the cpp tabulation code: In this lecture, it got accidently skipped but we have to use dp[i-1][j-arr[i-1]] instead of dp[i][j-arr[i-1]], watch the knapsack tabulation for more clarity. class Solution{ public: int subset_tabulation(vector&arr,int sum){ if(arr.size()==0 and sum!=0) return 0; if(sum==0) return 1; vector dp (arr.size()+1,vector(sum+1)); for(int i=0;i
@nitwaalebhaiya
@nitwaalebhaiya 3 жыл бұрын
Sir your way of teaching is just great. I don't have words to thank you🙏🏻🙏🏻🙏🏻🙏🏻
@kirtikhohal3313
@kirtikhohal3313 2 жыл бұрын
Your explanation is speechless!!, I only have one small doubt, in the beginning of the playlist, we were told that we can apply dp to those problems which usually have two properties, first overlapping sub-problem and second is optimality. I'm not able to grasp if this problem is asking for any optimal solution, that is largest, longest, min, max, etc...can someone tell me if it's asking for any optimal output...or if it is not, then what about these two mandatory properties??
@kirtikhohal3313
@kirtikhohal3313 2 жыл бұрын
@@KazHachiOreki Sorry, but your explanation doesn't answer my question.
@namashsharma7550
@namashsharma7550 Жыл бұрын
should i try to solve tabulation problems using recursion + memoization to better understand dp?? suggestions??
@navaugustt
@navaugustt 2 жыл бұрын
Best explanation watched on fractional knapsack based problem solving using DP 🤩🙌❤️
@praffuljavare1651
@praffuljavare1651 4 жыл бұрын
Great job correlating this problem with the knapsack problem! However I think you did not explain accurately, what t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j] actually means. From what I understand, the statement means that if the first i-1 elements are able to make the sum j, then great, else check whether it is possible to make the sum of j-arr[i-1] using the first i-1 elements. Please correct me if I am wrong.
@abhisheksuryavanshi9675
@abhisheksuryavanshi9675 4 жыл бұрын
please refer previous video on 0/1 knapsack
@priyarathore9266
@priyarathore9266 3 жыл бұрын
Best DP course on internet!
@aseembaranwal
@aseembaranwal 4 жыл бұрын
You applied divide and conquer in making columns on Paper. CSEian rock!!
@rajvijen
@rajvijen 4 жыл бұрын
Yo Bro, I thought same 🙂
@abhijitmukherjee1705
@abhijitmukherjee1705 4 жыл бұрын
I think the DP code that you have written for subset set part, in that there should be a slight variation. in the part where you have compared the two boolean value, at that position t[ i ][ j - arr [ i - 1 ]] will be t[ i - 1 ][ j - arr [ i - 1 ]], have a look or correct me if I'm wrong.
@adityadutta985
@adityadutta985 4 жыл бұрын
There's a pinned comment for this typo. Look at the pinned comment. It's just a typo
@paraslaul3307
@paraslaul3307 4 жыл бұрын
codeforces.com/problemset/problem/1113/A can you solve this problem of dp?
@SumitVerma-ln5nz
@SumitVerma-ln5nz 3 жыл бұрын
@@paraslaul3307 #include #include #define int long long int #define fio ios_base::sync_with_stdio(false);cin.tie(NULL); using namespace std; int dp[101][101]; int minFuelMoney(int n, int v) { for(int i = 3; i > n >> v; cout
@AltafHussain-on2oe
@AltafHussain-on2oe 4 жыл бұрын
aapka channel milne se pahle DP se darr lg rha tha but ab total darr khatm... thanks for explaining in very easy way that even below average student can also understand... Best wishes
@knandan6379
@knandan6379 4 жыл бұрын
mazaa aagaya bhaiya... aag laga diye.... iit-jee k coaching k din yaad aagaye.
@karoseha5521
@karoseha5521 Жыл бұрын
Hi, I'm watching the first 3 videos you teach about dynamic programming. Lectures are very good and easy to understand. However, my English level is limited. I hope you can turn on the subtitles in the next videos so that I can easily understand the article. Thank you very much!
@MOHITPATIDARRA
@MOHITPATIDARRA 3 жыл бұрын
Thanks sir ,because of these video, grasping concepts of Dp become easy.
@softwaredevelopment4392
@softwaredevelopment4392 4 жыл бұрын
May is near so can you tell exactly when are you going to upload the videos and on which topic . So that I won't learn those topics right now from other KZbinrs (waste of time + energy) . When are you going to complete this playlist of DP. ?
@ShivamKumar-cv7jv
@ShivamKumar-cv7jv 4 жыл бұрын
i think for this question recursion is more efficent, we just return where we find true and not recurse further.
@jaychotalia7542
@jaychotalia7542 3 жыл бұрын
@Aditya Verma , Sir as you said there are two ways of identifying DP question, 1) Choice 2) Optimal. But int this question they are not asking for any max or min value. Then how to know this can be solved via DP also ?
@Shourya_performs
@Shourya_performs 2 жыл бұрын
Actually the main question is minimize the length of the subset to get a desired sum. For example- arr[ ] : [2,3,4,5,10] sum : 9 possible subsets are : [2,3,4] and [4,5] but output should be of minimum length of subset so [4,5]. This is just a easier version of that problem.
@amitshah817
@amitshah817 3 жыл бұрын
Garda uda diye bhaiya🔥🔥
@022_cse-csdeepakkumarsain7
@022_cse-csdeepakkumarsain7 11 ай бұрын
Fabulous aditya bhaiya Great
@anushkabansal3176
@anushkabansal3176 3 жыл бұрын
Why did we wrote the Top-Down method? We should usually write Memoisation method right?As explained in previous videos.
@rishabhmalhotra2225
@rishabhmalhotra2225 3 жыл бұрын
Sir please add recursive + memoization approach for this and subsequent problems🙏🙏🙏🙏
@ankurbanerji6605
@ankurbanerji6605 6 ай бұрын
For anyone wondering why do we perform OR in place of MAX operation is because --> here we need to see if "ANY" combination of the array elements in the subset can sum up to the current target. If I found that 1 out of 10 subsets sum up to the current target then I can say it's TRUE even if the rest 9 subsets don't satisfy because I just need one.
@curiossoul
@curiossoul 3 жыл бұрын
So good. Could you please add a video on printing the subset. There are solns over different sites but would like one here
@kireeti1120
@kireeti1120 2 жыл бұрын
the similarities are explained greatly brother, thanks for your effort🙏
@tusharsingh2439
@tusharsingh2439 4 жыл бұрын
Great videos ! I had a doubt, in lecture 1 it was told that dp problems can be identified if they have two characteristics : 1) Choice 2) Optimial requirement(max,min,etc) in this problem what are we optimizing ? (in knapsack we were maximizing profit)
@TheAdityaVerma
@TheAdityaVerma 4 жыл бұрын
We have choices here !! For each element we have a choice whether we want to include it or not in our subset!!
@tusharsingh2439
@tusharsingh2439 4 жыл бұрын
Aditya Verma Thanky bhaiya, so all in all it should have either of the two characteristics?
@ankitdubey9310
@ankitdubey9310 3 жыл бұрын
@@tusharsingh2439 yes
@hiteshkaushik1468
@hiteshkaushik1468 2 жыл бұрын
@@tusharsingh2439 no "either of two" is a wrong understanding. A lot of optimization problems can be solved using greedy also. "Choice" and "Optimization" are rough identification markers that can be used to solve medium level DP problems. Many a times, these choice and optimizations markers are not visible directly in the problem statement. Another identification marker is this: If you try to come up with a bruteforce solution, you will need to evaluate all possible subsets of the given array. If array size = n, then total subsets = 2^n and this number is exponential. Trying out so many possibilities will obviously lead to a "Time limit exceeded" verdict and hence DP can be tried in such problems.
@himanshugupta4554
@himanshugupta4554 3 жыл бұрын
Nice explanation... I used different approach... I solved this as binary knapsack and because values of weights are not given , i took weight as value, then to check subset sum if t[n][sum]== sum then true, otherwise false
@shwetanknaveen
@shwetanknaveen 3 жыл бұрын
your initialization logic in both knap sack and here is costlt O(n*w) which however can be done in O(n + W) The whole point of DP is to reduce time complexity so I think we should do the same wherever possible
@PankajGupta-gh9cm
@PankajGupta-gh9cm 3 жыл бұрын
if we write the memoization code for this problem then after the base condition how to return the value if this already calculated since we create a boolean matrix then for each cell we have only two values either or false then how do we know if the current cell value is already calculated or not
@hishailesh77
@hishailesh77 4 жыл бұрын
Great explanation but it would have been great, if you could have started with Memorization and then proceed with top down . Anyway i have referred the comments of the people , who had given Memorization solution but couldnt understand that why everyone is using 2D memorization array whereas this problem could be solved with 1D array , the similar 1D approach we take in Fibonacci. Here is my Memorization solution using 1D, and would appreciate if you could help me to optimize if its applicable. public class DynamicProgramming { static int arr[]={2,3,7,8,10}; static int sum=24; static int[] mem =new int[arr.length+1]; static int isSubset(int arr[], int sum, int n){ if (mem[n] != -1) { return mem[n]; } else{ if (sum == 0) return 0; else if (n == 0) return 1; else{ if (isSubset(arr, sum - arr[n-1], n-1) == 0|| isSubset(arr, sum , n-1) == 0){ mem[n]=0; } return mem[n]; } } } public static void main(String[] args) { for (int i=0;i
@baldevverma5835
@baldevverma5835 3 жыл бұрын
table bhi optimised way me banai hai waah n/2. true coder
@RohitSharma-lz8db
@RohitSharma-lz8db 4 жыл бұрын
Great explanation. But How would we do the memoization of this problem?
@life_of_anjali
@life_of_anjali 4 жыл бұрын
int subsetSum(vector&arr,int sum,int n,vector&t){ if(sum==0){ return 1; } if(n==0){ return 0; } if(t[n][sum]!=-1){ return t[n][sum]; } if(arr[n-1]
@mainaksanyal9515
@mainaksanyal9515 4 жыл бұрын
Bhai, aap bole ki isko kaise print karwana hai (sahi wala pattern) wo bhi dikhayenge. Kya wo kisi aur video mein hai? Wo bhi DP se hoga kya? Edit: Kya humlog column wise upar jake jaha pe True---> False mein badal raha hai wo element leke, uska weight minus karke uske upar wale row mein weight minused position mein jaye aur fir column mein dekhe ki true kaha false mein change ho raha hai...aise trace karke elements dhund sakte hai kya? Just thought of it!
@Ayush-jz5um
@Ayush-jz5um Жыл бұрын
20:09 why did we use OR operation........... can we use AND or something like that... please someone clear my doubt.
@AkashKumar-tb9jv
@AkashKumar-tb9jv Жыл бұрын
beacuase in AND both condition should be true for result as true. but in OR one true and one false result true.
@gamerhu7462
@gamerhu7462 3 жыл бұрын
JUST A REQUEST NEVER STOP UPLOADING KCH BHI KOI BHI TOPIC CHLEGA !!!!!! the way u make us understand things are amazing!!!
@Akshitgupta1
@Akshitgupta1 4 жыл бұрын
Summary at the end was an awesome wrap up💯
@aminesouley8252
@aminesouley8252 2 жыл бұрын
i just wish i was idian to understant what he is saying i get the idea but just wanted to understant directly the video neverless great job man
Equal Sum Partition Problem
18:01
Aditya Verma
Рет қаралды 369 М.
9 Count of Subsets Sum with a Given Sum
20:49
Aditya Verma
Рет қаралды 366 М.
黑天使只对C罗有感觉#short #angel #clown
00:39
Super Beauty team
Рет қаралды 36 МЛН
Гениальное изобретение из обычного стаканчика!
00:31
Лютая физика | Олимпиадная физика
Рет қаралды 4,8 МЛН
VIP ACCESS
00:47
Natan por Aí
Рет қаралды 30 МЛН
43 Egg Dropping Problem Recursive
30:10
Aditya Verma
Рет қаралды 170 М.
3 01 Knapsack Recursive
21:04
Aditya Verma
Рет қаралды 625 М.
6.2 Sum Of Subsets Problem - Backtracking
12:19
Abdul Bari
Рет қаралды 1,5 МЛН
Target Sum Subsets Dynamic Programming | Subset Sum Problem
29:20
10 Minimum Subset Sum Difference
46:41
Aditya Verma
Рет қаралды 398 М.
L10. Subset Sum I | Recursion | C++ | Java
24:25
take U forward
Рет қаралды 382 М.