Target Sum Subsets Dynamic Programming | Subset Sum Problem

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 where we are required to find the subset of an array with sum equal to a given target. In this problem
1. You are given a number n, representing the count of elements.
2. You are given n numbers.
3. You are given a number "tar".
4. You are required to calculate and print true or false, if there is a subset the elements of which add up to "tar" or not.
For a better understanding of the problem, click here: • Target Sum Subsets - Q...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#dp #targetsum #dynamicprogramming
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@shreyasingh7833]

I don't think anyone teaches the problem this deeply and with so much clarity ! Thank you so much sir for providing these video solutions .

[@puccaepisodes1509]

This cricket concept goes very well with DP. Awesome way to make us understand the solution. You are an amazing teacher!

[@umaradhami]

Best content on DS and algo on the internet right now

[@Pepcoding]

Thankyou beta! 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. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms ) Keep learning and keep loving Pepcoding😊

[@KhairulMia-tr2jv]

sir never write comment to any tutorial in youtube but today i am really impressed by your teaching method ,thank you so much

[@closer9689]

Next Level Explanation!!!! This is the best video on KZbin to understand this question:) NO DOUBT ❤👌🤌 Thank you very much Sir!!!😇🙏

[@aditikhare1784]

I love watching your videos. You make the solution so simple and explain everything so clearly. Keep up the good work buddy!

[@mihiradarsh7604]

I always used to run away from dp, thought it was hard, but after seeing your videos, I feel blessed. Thankyou Sir :)

[@sumitmishra848]

finally i understood this . you have some serious teaching skills . Thanks a lot for this video !!!!

[@vsbelieve]

The level of understanding you have for these topics is amazing sir 🔥thanks you sir for providing this for free.

[@starmist808]

for any problem, i first search on pepcoding. You are amazing Sir! Your concepts and way of teaching are more retained by me, as compared to teachings of other teachers on youtube.

[@watchforabhay]

Your understanding and expression of understanding(teaching) is great! Wish i could learn DP from you directly

[@pijushbasak4273]

I do good programming, but when it comes DP, recursion I got confused. I have started my DP, Recursion journey from so-called premium channels, but all went in vain...Now I find your explanation, I am satisfied and very happy because you explain how I wanted to learn from deep. Thank you very much.

[@maniac0224]

Amazing lecture. Best explanation on KZbin.

[@shubhambhardwaj2399]

Sir you are a good singer along with coder 👍

[@murtuzashareef7906]

No other channel no other, nowhere can anyone find such top quality content

[@sanyamkothari4469]

maine itna smjha iss concept ko lekin har baar upar se; lekin sir ne jaise hi test match ka example dia, 2 sec me is ques ka {how} smjh gya :)

[@suzanaangboo2448]

Its 30 min video and you are describing the concept for 20 min and rest code :). Really Appreciate your work.

[@ayushsaxena9386]

you are the best teacher on youtube

[@therohanjaiswal]

Couldn't find a better explanation. Thanks a lot.🤩

[@pritishpattnaik4674]

the depth in which you clears our concept is amazing and can write code by my own

[@Pepcoding]

Nados.pepcoding.com pe experience aur acha hai

[@MegaArvind111]

Good Content , with due focus on traversal of the logic till the end . Keep doing gr8 work Sumeet

[@codewithrebel1286]

First time i understand that how this 2-d array works. Thank you sir..

[@Pepcoding]

I am glad you liked it. I hope that you are watching the videos 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/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@amazinglife5400]

Sir, you are one the best and number one coding tutor in India. Your expertise & amazing talent in teaching is just another level. Please keep making these videos as your way of doing deep analysis and approach is just next level which is unmatched by any tutor across India. Aapka support aur blessings chahiye bas 🙏

[@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😊

[@pranayreddyannam188]

got clarity of what going in the matrix, Thank you sir

[@akrammohammed1167]

This is the best explanation of the tabular dp approach. ❤️

[@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. If you like our efforts, we request a review - g.page/Pepcoding/review?rc

[@snehalkumar.singh.cse2070]

While you were filling in the table i found that if a column consists of true then all the cells of the columns below the specified one consists of true hence while filling in dp[r][c] we can make a check like if(c==tar and dp[r][c] == true) return "true"; which will reduce the complexity a little bit or significantly, {depending upon the test cases} By the way, the session was so engaging.

[@vedantvalsangkar2091]

Best Explanation of tabular method to solve dp problems !! Really best content!! Keep going sir! I want to see memoization method also!

[@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. keep watching and keep loving Pepcoding😊

[@shwetajha5356]

Finally I understood How elements are inserted in the table... & The example of cricket made it easier for me.. Thanks sir...

[@Pepcoding]

Glad you love the explanation. For better experience and well organised content sign up on nados.io and don't forget to follow us on Instagram instagram.com/pepcoding/

[@kushagra4401]

thank you so much sir! your explanation is superb 😍

[@eshanikabhattacharjee383]

awesome vid! how to modify this to count no of subsets or return the required subsets

[@harshitgupta5887]

I am curious about whether the time complexity of above explained tabulation and the memoization approach using recursion would be same or not?

[@prasads7530]

Thank you so much Sir..Apka khoob dhanyawaad. You are a great teacher Sir !!

[@akhilesh59]

Great Explanation Sir! Thank You..

[@namanshah2688]

great explanation sir ! thankyou for your valuable content

[@shivangsharma4873]

Kya gadar example sir......Insane level explanation , pehli baar DP ki problems doable lgg rhi hain.... All thanks to you Sumeet Sir

[@Pepcoding]

Thank you so much!! pdtee rhiee or bdtee rhiee

[@shivangsharma4873]

@@Pepcoding Bss sir aap isi tarah bdiya examples k sth smjhate rhiye or hmara kalyan krte rhie :p

[@rohitbadhai8219]

I think as the tick marks are getting forwarded for a column so at line 32 we can simply check at i instead of i-1. Btw Amazing Explanation!

[@sagarbanga8188]

what a brilliant way of teaching !!!

[@Pepcoding]

Thank you for appreciating. keep motivating, keep learning and keep loving Pepcoding😊

[@samarthsingh663]

Sir i had one confusion that using this approach how can we print that subset. Will we be inserting it into the vector right when we get true in the starting...matlab ye h ki i am not able to locate that how we will do this.

[@mayursuhasiya8613]

Amazing explanation sir... i was very confused with the formula of it. and you made it very clear. Thank you so much!!!

[@Pepcoding]

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

[@rishabhgoyal2835]

sir apke notes me likha hai """for negative numbers , make dp where columns range from -target to target """" yeah samaj nhi aarha , negative numbers ko kaise handle kre .... sir mene khud se dry run kia h to yeah result nikla hai ki array me agar negative values hai then,... array ki max value jitne columns banege ( + - dono me) . ex arr is 4 , 3 , -2 , 5 and target is 3 then columns will be -5 to 5 ... is it right sir ? correct me if not.. sumeet sir @pepcoding

[@sudhanshusharma9123]

Thank you sir for solving the complete table hence providing a detailed and understandable explanation. I wanted to ask whether it will be sufficient to provide this (tabulation) approach in a technical interview.

[@Pepcoding]

Yes, sure

[@sunnygoswami2248]

Thankyou Sir, it was a great analogy.

[@24381498]

shandar content hain sir.. thanks Sumeet sir.

[@arnabmallik7978]

Beautifully explained. Thanks a lot.

[@Pepcoding]

Most welcome!

[@rajeshdas2295]

awesome sir!!!! nice explanation got it clearly!!

[@kaushalsharma9777]

Pure gold♥️, belated birthday wishes sir

[@Pepcoding]

Thanks a ton

[@ghanendrapanwar165]

Sir for this question do we have any other approach also.

[@vipsclassicalboy]

O bhai, simply so awesome

[@prahladrana6391]

sir,can this approach also be used to print the subsets for the target sum rather than just printing true or false?

[@Pepcoding]

yes, that is an extended question. That will need graphs and DP.

[@vihaansingla5088]

sir iss problem ko recursion with dp se bhi solve kar skte hain

[@MahimDashoraHackR]

2 hours se buss video dekhke smjhne ki koshish krra tha finally agya .

[@Pepcoding]

Doubt support chaie to nados.pepcoding.com se dekho same video ko

[@cr7johnChan]

Best explanation in the world

[@shreyanshsharma8909]

I mean, really, itna sahi explaination mene aaj tk nhi dekha. Aap best ho. Please aur bhi algos k videos bana do please. Aap har variety k dp k problems ka video bana do yaar, dp achche se samajh aa jaayegi. It would be really helpful

[@Pepcoding]

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😊

[@AYJ959]

underrated he channel pta ni kyu but ty sir mza agya

[@Tarunkumar-si4im]

Nice explanation sir❣️

[@sankalpmehadia9252]

Sir if i do this question using arraylist why is is showing TLE

[@Kuldeep-rn9ts]

Best explanation sir, Thank you.

[@Pepcoding]

keep motivating, keep learning and keep loving Pepcoding😊

[@0anant0]

Very good explanation! For cricket analogy, you could have chosen a subset of 4,2,6,1,3 and then said that there are ppl on the team who score ONLY 4, ONLY 2, ... or ONLY 3. That way, when you say remaining team, it is easy to visualize that a person who ONLY scores 4 cannot score 1,2,3,5, etc. -- -- this is a similar approach to when you have coins of specific denominations. Overall, you made it very easy to understand how we go to (items - 1), (sum - current elem value), etc row, col. for the include/exclude scenarios. And props to your tremendous patience in explaining the filling of all 11 * 6 = 66 cells!

[@Pepcoding]

Thankyou beta

[@closer9689]

You are reallyyyyy Underrated Sir!!!!!!🙂

[@abhishektanwar7902]

Sir which approach is better for solving Recursion(Memoization) or Top down.

[@shreyashkarlalsahu9248]

Top-down is better if you need the final value only or need one specific output, but if you want to output multiple values then go for memoization as it stores the value for each element operation.

[@RishabhJain-hr6sz]

Amazing explanation with Analogy sir. 👌👌

[@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 )

[@shubhammittal4389]

Relating it to criclet and then explaining

[@Pepcoding]

Thanks a ton. For better experience and best organised content visit on nados.io. Also you can post your doubts on community tab on NADOS.

[@ashutosh1541]

kisi ko hickhi aa rahi background me.. amazing work sir i had been struggling with this coin change and entire tabular form of dp ... i get the recursive dp very easily but the itravtive one i havent found anyone better than you so thank you sir ...

[@coderguy339]

wah sir wah !!!! batting team run what a fantastic explanation i couldn't stop myself from putting comment. DP, graph is toughest pls cover too many ques on these topics. and yes pls do memoization (recursive approach) also. from 500 subs to 5k subs i m seeing the transformation!!

[@Pepcoding]

Thank you. Bro, linkedin ya fb pe ek post daal do channel ki. Bacho ko pta chal jaega. Will redo all DP in memoization as well. Par sath nahi, video bhot lambi ho jaegi.

[@coderguy339]

@@Pepcoding Yes sir i m sharing ur channel in my clg grp.

[@jenishchetankumarpatel1662]

please bring one video of dfs and bfs cases in every data structure

[@codemaestro9904]

Sir kya ye approach array mein negative numbers k liye bhi work kregi? If not, toh kya hume memoization use karna hoga?

[@Pepcoding]

haji.. bs index shifting krni hogi.

[@abhishek__anand__]

Great Explanation

[@harshpratapsingh3736]

will also work if the array has repeating elemets

[@ayushsaxena9386]

in the same problem how to return 2d array with subsets of k?

[@himanshuhota01]

Thank you so much sir ,🙏🙏🙏🙏🙏🙏🙏🙏

[@jenishchetankumarpatel1662]

really greatt and thank u sirrrr

[@himanshuhota01]

aapke jaisa teacher banna chaunga sir agar kabhi teacher banu to🙏🙏🙏🙏🙏🙏

[@amandixit3555]

sir is it necessary to go upto last row, i mean if managed to find subset which gives target sum like in above qtn for second last row we achived the target sum, uske baad Break karke loop ke bahar aa sakten hain na sir ?

[@Pepcoding]

aa sakte hain beta.

[@kms8320]

super-duper hit explanation sirrrr👌🙌🙌🙌

[@Pepcoding]

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

[@saraswansinha1132]

Awsome Video!!!! Sir, ek doubt h.. meine jab isko solve karne k approach liya meine.. Dp ke rows mein Sum li..(0-10) aur columns mein (0-6) ..code bhi accordingly chnage kiya h...but answer ni aa rha..koi solution bhi ni mil rha Internet pe iska..Ye pata kaise chalega ki rows mein kisko lena h aur ol mein kisko lena h?

[@aashishgoyal1436]

Beautiful explanation...thanks a lot sir What if the target sum is big say 100 or 1000.. do we create that many columns??

[@Pepcoding]

Yes, we will need more columns. We can optimise the rows. Actually we can do it with just 2 one d arrays.

[@anshulgarg6146]

Bhot hi zabardast samjhaya sir aapne!!

[@Pepcoding]

Thankyou beta! 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/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@jatinmaheriya2343]

Very good singing 😇👏🏻

[@sarangr8624]

Amazing teacher 🙏🏿

[@Pepcoding]

Keep learning, Keep growing and keep loving Pepcoding!😊

[@nostakash]

Sir humko kaise pataa chalega ki humko gap method use krna hai ya nhi

[@RahulKumar-pk7ht]

Sir, i like your singing❤️❤️

[@sanjanachowdary2087]

ur tutorials are awesome. please give ur patreon account in the description.

[@ishanpatni2684]

sir why did we take the first cross row, what was its use??

[@Pepcoding]

kyunki dp ki table bharte hue upar wali row mei jana padta hai. extra case handle karne se bachne ke liye.

[@damaanilkumar391]

fab teaching

[@aayushsharma5156]

Sir first question mei dp ka use ache se smjh aa gya tha kyuki apne ache se smjhaya tha k hme us question ko sove krne k liye dp kyo use krni chaiye. Sir vaisi he explanation( mtlb ye k dp regular approach se better kaise h) agr is question ki bhi mil jati to isme dp ka use ache se smjh ata. vaise ab video to bn chuki h , pr aap dp ka use pls ya to comment section mei bta dijiye ya discription mei.( Pta nhi km jo khna cha rha hu vo aap is comment se smjh payenge ya nhi)

[@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.

[@shivanikapoor9305]

Nice content.. which editor are you using?

[@Pepcoding]

This really means a lot, Thank you for your immense support and the most important thing you guys liked it. For much better content visit on nados.pepcoding.com, you can also post such query on community tab. Don't forget to follow us on Instagram instagram.com/pepcoding/

[@chintu225]

very well explained...But I am wondering whether this is possible only when target is small enough. How about if the numbers in the array are like [200,300,45,487,454] and target is 500. Filling 500 column table can be more time complex r8?

[@Pepcoding]

Thankyou! Buddy, 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.

[@elroinoronha433]

Yo Laxman , did you find an answer for the question you asked ??

[@decostarkumar2562]

What if there are negative elements?

[@rakshitdevra7060]

Cricket method is best for understanding ❤️❤️❤️

[@Travellingwithaayu]

Dimag m chap gyi h algo.. hats off👏👏

[@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

[@0_0-0_0.]

Feedback : Sir i think agar cricket wala concept na lakar normal samjhate to jaldi Samajh aata. Cricket wale se little bit confusing lag raha tha. Btw great Content sir Thank you so much ❤️

[@saarthjhaveri8716]

sir, superb way of explanation

[@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. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here kzbin.infoabout?view_as=subscriber

[@saarthjhaveri8716]

@@Pepcoding donee

[@ayushsaxena9386]

thanks sir.

[@apoorvamittal1379]

How will we extend this solution for negative elements in array ?

[@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.

[@nitishkesarwani4237]

can anyone share the bottom up approach of this question?

[@ditu-kunalsarda6863]

Beautiful Explaination! Initially I used the Two Pointer Algo. 4/5 test cases passed could have never thought of this approach but abb aaisa related question aaya toh apna cricketer SIX maarega!

[@Pepcoding]

best of luck. ye 5 questions ka set hai poora. Order me kijiega.

[@AnkitSharma-wj2tb]

great explanation again sir

[@Pepcoding]

Thanks and welcome

[@gauravkumar0777]

Sare question hm tabulation se karte h memorization ka use nahi karte kya sir??

[@Pepcoding]

For better experience and well organised content. visit - nados.pepcoding.com Also you can post your query on community tab. Don't forget to follow us on Instagram instagram.com/pepcoding/

[@hrishitsarkar6388]

thanks sir

[@vaibhavmishra6954]

sir jinko khelna hi nhi aata me un players ko team me hi nhi lunga XD jokes apart great explanation