7 Subset Sum Problem
HTML-код
- Опубликовано: 7 фев 2025
- Subset Sum Problem(Dynamic Programming)
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.
PROBLEM STATEMENT LINK:www.geeksforge...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Sir just for confirmation - 20:58 me t [ i - 1 ] hona chahiye na(Because we have processed the last element)?
Yes yes of course, thats just a typo !! Wait here let me pin your comment to help others !!
This playlist is really helpful.Thanks Sir.
@@TheAdityaVerma Hey, You can add correction in the video as a popup. Great Work Anyways.
@@harshitanand8216 i will always start from 1 since we already did the initialization for i = 0
Thanks Keerat! Wohi soch raha tha
Watched all the ads just to support you! I usually have ad blocker. You are killing it!
Purushhottam Prashant hai bhai tu 🙏 jokes asides, Thanks a lot brother, this world really don't have many people like you :D 🙏
@@TheAdityaVerma 🤣🤣🤣🤣🤣🤣
@Saswat Pattnaik uBlock Origin Chrome Extension.
Better buy a youtube premium
@@ScienceSeekho better use another browser where there are no ads for any type of content
Mind blowing explanation, I usually do not comment but this sort of material needs a big applaud.
if you got placed now,please refer me
@@raunop8208 koi ni hota refere bhai padhleeee
@@raunop8208 experience se bata raha hu
@@raunop8208 She in Microsoft bro
@@raunop8208 bhai Teri lag gyi to hume refer krde ab XD
7 of 50 (14%) done! Very nice explanation of initialization and the summary at the end was a great wrap-up, tying everything together.
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.
But I think he is from MNNIIT Alahabad
@@PalakMittal NIT ; )
@@ananypandey1310 Yeh! My bad 😅
@@PalakMittal No, he is from MANIT Bhopal
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]
my code failed exactly in that case and im glad that someone mentioned like u mentioned the corrected one
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.
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.
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..
I"ve done course from coding ninjas but this playlist makes me understand dp easily , serioulsy you are an inspiration
Thanks for the advice.Gonna complete dp from here and then go back to that course.
So many institutes will fail to explain like this. Hats off to you
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!!!!!!
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 .
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!!!
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 🙏🏽
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..
So nice of you !! Thanks was really a creative compliment 😂✌️
@@TheAdityaVerma link g4g you attached is slightly different , aint it ?
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!!
But it doesn't pass all the testcase
@@yatri6329 whats the problem?
I might help
Best channel on youtube . On my way to finish the dp playlist
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)
This is genuinely the GOD level explanation !! Thanks Bro
Really very helpful . I don't know how many times I have come back to re-watch this playlist.
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 :)
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
@@arch3994 wtf
@@arch3994 lmao
Best teacher ever... Thanku for helping all of us..
Soon your playlist will come in the top 10 , best wishes. I just want you to add more videos on Algorithm :)
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 !! ✌️❤️
@@TheAdityaVerma How is your job going. You mentioned in previous video that you got 16L package.
Solved my first DP question after watching your tutorials. Huge Thanks bro!
Kudos to u brother.
I too hv solved my first Dp problem 2 days back..
I knw this feeling man.
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!
The best video ever on dp..The way you are teaching....Is just amazing
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.
I was able to initialise dp array by using recursion. No one tells this thing is comming from recursion base condn. Great work man.
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 !!!
Thanks Brother !! Do share where ever you feel right to help the channel grow !!
great work brother. Kahi ni mili esi understanding, jitni teri basic videos se mil gayi. Thanks
@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];
At last found someone who noticed. Thank you for your answer. Can you explain how the corrected code works. I couldn't get it
Solved this without even seeing the video. Knapsack explanation🔥🔥🔥🔥
nobel prize
bhai tu meri zindagi ka pehla aur iklauta pyaar hai. Tere channel ko meri duaein lage. Lagni zaroori bhi hai, mai heejda hu
videos dekh kr apki mn krta hai bs dekhte hi jao....best person
ye to kuch kuch 5- start jese ho gya - "khao aur kho jao" 😂😂
The best explanation in the youtube on DP where I found the explanation even in Matrix wise ,where no one does..
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
In which language u code??
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)
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 :)
Haha Thanks Archana !! I love his accent tho 😂😂😂😂I mean who doesn't right? 😅
@@TheAdityaVerma but you teach as a elder brother or a friend ...
@@TheAdityaVerma thank u
How to select which term to take as row and column....
What if we take vice versa???
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))
Can you Post the recursive code solution ! Thanks
@@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]
Yaar!!!!. Ek he toh dil hai kitne baar jitoge.
love your videos. If you did not made this playlist I might have never understood DP.
Aditya, I am not exagerating. You truly deserve the Dronacharya award had they been giving it for academics.
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
Bhaiya teacher ho to aapke jaisa !! Maza aa gya !! 😁
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.
I am a GSOCian but my advanced CP isn't good enough...This is really helpful....Thanks a lot @Aditya Verma :)
I saw many dp videos, so far this one is the best. Thanks for such great explanation. Keep posting such videos!
thank you for making this excellent video!! We all are grateful to you! Soon I will get a good job. Thanks to you!!
One of the Best tuturial>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
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.
they don't like to understand things
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.
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)
@@nishantsethix 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.
Sir your way of teaching is just great. I don't have words to thank you🙏🏻🙏🏻🙏🏻🙏🏻
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] , ...)
sahi baat mere coder!!
nobel prize laya jae bhai k liye😪😐😐
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
Completed 7 out 49 video....I will comment upto lecture 35 ., today on every video for sure..
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
You are doing a great job bhaiya....God bless you..
u r best bro.. i have learnt from many youtubers but you and traversay media are best .. ur basic is clear..
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
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
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 ?
Yes he has patreon now, check new videos for link.
@@MALIWAL1000 yes, already a member
have you got TLE with memoization?
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
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.
please refer previous video on 0/1 knapsack
Literally thanks a lot from the bottom of my heart
Best explanation watched on fractional knapsack based problem solving using DP 🤩🙌❤️
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??
@@KazHachiOreki Sorry, but your explanation doesn't answer my question.
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.
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
This was a really nice explanation. I was stuck in this from a day , couldnt relate. Thanks 😁 please keep making videos
Thanks !! I am glad it helped you !! Do share and subscribe.
@@TheAdityaVerma bhai aap legend ho please video banao aur
Hi Aditya, need a help with the below question.
Samu is playing a shooting game in play station. There are two apples to aim in this shooting game. Hitting the first apple will provide her X points and hitting the second apple will provide her Y points. And if she misses the apple she chose to hit, she won’t get any point.
Now she is having N coins and each shoot will cost her 1 coin and she needs to score at least W points to win the game.
Samu don't like to lose at any cost. At each turn, she has two choices. The choices include: -
Hitting first apple with probability P1 percent. However, she might miss it with probability (1-P1) percentage.
Hitting second apple with probability P2 percent. However, she might miss it with probability (1-P2) percentage.
She would like to know what is the maximal expected probability (as a percentage b/w 0 and 100) of winning the shooting game.
Note:
Choosing to hit any apple is entirely her choice. Both are independent events meaning P1 + P2 may/may not exceed 100.
Output must contain 6 digits after decimal.
Thanks sir ,because of these video, grasping concepts of Dp become easy.
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
Bro please make videos on tree also ...🙏🏻🙏🏻it will be helpful for my interview....make all videos on trees
It would be really nice if you can dry one problem at the end of the video. Keep the good work going!
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.
Best DP course on internet!
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!
Fabulous aditya bhaiya Great
i think for this question recursion is more efficent, we just return where we find true and not recurse further.
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
i 'm watching his video and then tushar's video to get a clear undrstanding
this video is good for basics and then check tushar's video to see how the table gets populated (if you have doubt on the table population )
yeah. No explanation of how the solution is being written atleast.
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
sir aap khud bole ki pehle recursiion likho tab memo tab tabulation ..aur khud direct tabulation btane lage ...aishe kaishe hoga
the similarities are explained greatly brother, thanks for your effort🙏
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!
Sir please provide the code of the question you have included in the description because I am getting stuck since more than 1 hr.
It is giving TLE error , for sample test cases answer is correct
Yes sir please provide
Hi, I found a small issue in your final subset-sum solution. you had written t[i][j] = t[i][j-arr[i-1]] || t[i-1][j] but it should be t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j] according to me. please correct me if i am wrong. Apart from that i like the way you had explained.
Yeah right there was a small error
mazaa aagaya bhaiya... aag laga diye.... iit-jee k coaching k din yaad aagaye.
Awesome explanation sir!
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🤗
Sir, i am sure you are a very busy person but i tried all channels and honestly given this covid only you can help us in securing a job. It's a humble request please keep making videos. You are my last hope for getting a grasp at algos please.
You created the table (7:55) with a dp approach lol!! Awesome Videos!
should i try to solve tabulation problems using recursion + memoization to better understand dp??
suggestions??
Garda uda diye bhaiya🔥🔥
sir, your teaching skills are excellent
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 RUclipsrs (waste of time + energy) .
When are you going to complete this playlist of DP. ?
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)
We have choices here !! For each element we have a choice whether we want to include it or not in our subset!!
Aditya Verma Thanky bhaiya, so all in all it should have either of the two characteristics?
@@tusharsingh2439 yes
@@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.
@Aditya Verma how to print all the subset after we create the matrix....... ??
take a global list and fill that once you reach the answer
@@HarshitGupta005 how we can fill
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?
Yes , i wrote the recursive function first , and then memoized it, and then I went on to write the actual iterative code
@@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]
yes, I agree with this. Starting from a recursive solution seems more understandable and good in an interview.
So good. Could you please add a video on printing the subset. There are solns over different sites but would like one here
bhai ne to table banane ka logic dediya :D