Subset Sum Problem using Dynamic Programming | Data Structures and Algorithms

Learn how to solve sunset sum problem using dynamic programming approach.
Data structures and algorithms playlist link:
/ @jennyslecturescsit
Jenny’s Lectures CS/IT NET&JRF is a Free KZbin Channel providing Computer Science / Information Technology / Computer-related tutorials including Programming Tutorials, NET & JRF Coaching Videos, Algorithms, GATE Coaching Videos, UGC NET, NTA NET, JRF, BTech, MTech, Ph.D., tips and other helpful videos for Computer Science / Information Technology students to advanced tech theory and computer science lectures, Teaching Computer Science in Informal Space. Learning to teach computer scienceoutside the classroom….
KZbin a top choice for users that want to learn computer programming, but don't have the money or the time to go through a complete college/ Institute / Coaching Centre course. ... Jenny’s Lectures CS/IT NET&JRF is aFree KZbin Channel providing computer-related ... and educate students in science, technology and other subjects.
If you have any further questions, query, topic, please don't hesitate to contact me.
Main Topics:
Algorithms, Applied Computer Science, Artificial Intelligence, Coding, Computer Engineering, Computer Networking,Design and Analysis Of Algorithms, Data Structures, Digital Electronics, Object Oriented Programming using C++/Java/Python, Discrete Mathematical Structures, Operating Systems Computer Simulation, Computing, Bit Torrent, Abstract, C, C++, Acrobat, Ada, Pascal, ADABAS, Ad-Aware, Add-in, Add-on, Application Development, Adobe Acrobat, Automatic Data Processing, Adware, Artificial Intelligence, AI, Algorithm, Alphanumeric, Apache, Apache Tomcat, API, Application Programming Interface, Applet, Application, Application Framework, Application Macro, Application Package, Application Program, Application Programmer, Application Server, Application Software, Application Stack, Application Suite, System Administrator, Ada Programming, Architecture, computer software, ASP, Active Server Pages, Assembly, Assembly Language, Audacity, AutoCAD, Autodesk, Auto sketch, Backup, Restore, Backup & Recovery, BASH, BASIC, Beta Version, Binary Tree, Boolean, Boolean Algebra, Boolean AND, Boolean logic, Boolean OR, Boolean value, Binary Search Tree, BST, Bug, Business Software, C Programming Language, Computer Aided Design, Auto CAD, National Testing Agency, NTA,CAD, Callback, Call-by-Reference, Call by reference, Call-by-Value, Call by Value, CD/DVD, Encoding, Mapping, Character, Class, Class Library, ClearCase, ClearQuest, Client, Client-Side, cmd.exe, Cloud computing, Code, Codec, ColdFusion, Command, Command Interpreter, Command.com, Compiler, Animation, Computer Game, Computer Graphics, Computer Science, CONFIG.SYS, Configuration, Copyright, Customer Relationship Management, CRM, CVS, Data, Data Architect, Data Architecture, Data Cleansing, Data Conversion, Data Element, Data Mapping, Data Migration, Data Modeling, Data Processing, Data Scrubbing, Data Structure , Data Transformation, Database Administration, Database Model, Query Language, Database Server, Data log, Debugger, Database Management System, DBMS, Data Definition Language, DDL, Dead Code, Debugger, Decompile, Defragment, Delphi, Design Compiler, Device Driver, Distributed, Data Mart, Data Mining, Data Manipulation Language, DML, DOS, Disk Operating System, Dreamweaver, Drupal, Data Warehouse, Extensible Markup Language, XML, ASCII, Fibonacci , Firefox, Firmware, GUI, Graphical User Interface, LINUX, UNIX, J2EE, Java 2 Platform, Enterprise Edition, Java, Java EE, Java Beans, Java Programming Language, JavaScript, JDBC, Java Database Connectivity, Kernel, Keyboard, Keygen, LAMP, MySQL, Perl, PHP, Python, Logic Programming, Locator, Fusion, Fission, Low-Level Language, Mac OS, Macintosh Operating System, Machine Code, Machine Language, Metadata, Microsoft Access, Microsoft .Net Framework, Microsoft .Net, Microsoft SQL Server, Microsoft Windows, Middleware, MIS, Management Information systems, Module, Mozilla, MS-DOS,Microsoft Disk Operating System, Magic User Interface, MUI, MySQL, Normalization, Numerical, Object-Oriented, Open Source, Solaris, Parallel Processing, Parallel, Patch, Pascal, PDF, Portable Document Format, Postgres, Preemptive, Program, Programming Language, QuickTime, Report Writer, Repository, Rewind, Runtime, Scripting Languages, Script, Search Engine, Software Life-Cycle, VBScript, Virtual Basic Script, Classes, Queues, Stack, B-Tree, Computer Science, Information Technology, IT, CSE Quora profile: www.quora.com/profile/Jayanti...
Find me on Instagram: / jayantikhatrilamba

[@justadev____7232]

Best explanation I've found on this algorithm. I spent over 2 hours watching other videos without being able to grasp it. Came across this one and it clicked!! Thank you!!

[@vinodkumar-ds2po]

I came across lots of videos on the internet for this particular problem, but none of them were able to explain in such a decent and nice way like you. Very well explained, thanks a lot :)

[@nikmat]

Kidding?

[@pg9645]

@@arunakampati4365 Worst hai woh. Bas outdated C language ka incomplete pseudocode deta hai. Waise toh hum bhi explain kare par ek code karke dikhaiyye ? Wastage of time on his videos

[@ritupornaduttaroy9205]

Dhjrfklkyggfcszcjo

[@sdwysc]

@@pg9645 C language is outdated?

[@ABCD-gn5uw]

@@sdwysc to be honest he should have shown the implementation as well. i love his way of explaining but a implementation would be cherry on cake.

[@baibhavvikas1767]

Thank you ,mam for such an amazing explanation .It solved all my doubts. Apart from other who just showed how to write code u explained how to fill the table in a really fantastic way

[@KhushiJain-xx2yk]

Best tutor I have ever seen on KZbin 🤗🤗you're amazing ma'am

[@RFV7HD]

*Amazing explanation saved my lot of time thanx mam* :)

[@smilingsna4462]

Thank you ma'am so much 😊 I searched a lot about this problem I didn't find a single solution as your so thank you so for explaining it in detail 🙂🙂

[@jaewanjang4469]

Thanks for great interpretation!

[@velakuruday]

Thank you sister. You explained in a slow and clear way.

[@GulshanKumar-jd2dm]

Nice explanation mam. U also make easier for writing code. Lot of thanks mam😊😊

[@priyankataneja7347]

This video explains whether sum exists or not. Can you explain how can we find pairs. Which all set of elements form the sum,. For Example - {1,3,5,7,10,2,6} - Target Sum - 12 Answer should be - (1,5,6) (10,2 )(5,7)(6,2,3,1). How can we find this thing from this matrix?? Could you please explain this??

[@touchskyfacts1391]

Refer to her next video ..

[@kulkiratsingh7924]

which one? Can you please share the link to it? @@touchskyfacts1391

[@rahuramrt8051]

Link please

[@user-mw9vq6me7e]

@@touchskyfacts1391 please bro send me the link?

[@deepanshusingh2352]

Beautifully explain by you

[@AmitSingh-1916]

Thank you ma'am👍 for this concept🙂

[@HXYZZZ]

Thank you. well explained.

[@c.danielpremkumar8495]

Excellent !

[@abhishekrathore2352]

Great Explanation

[@blackfromabove9383]

Many many thanks!!

[@chenghaowang8759]

thank you! very useful

[@tienthanhpham4596]

Your algorithm videos have helped me alot, I'm grateful to you. If you have time, could you make some videos of backtracking?

[@rishabhkumar7179]

Maim please upload the second video of this to find out the particular subset 🙏

[@amandeep0148]

Tc mam 🤟🏻🖤 its very useful lect. Mam .thank you very much .🖤

[@sugatasaha4423]

great explanation

[@AbhishekKumar-im2xd]

another method is using bitsets::) ll N; cin>>N; vector arr(N); for(auto& it : arr) cin>>it; bitset b(0); b[0]=1; for(auto x : arr) b |= (b

[@vaibhavgarg4267]

@Jenny it will be helpful if you can explain how to deduce that we should be creating table in this manner? And, how it is concluded that we need to use this formula? This would help in actual logic building.

[@SEVERANCE850]

Probably she doesn't know and have only by hearted it and started teaching

[@yadwindersingh9722]

Very Good ma'am

[@abhinashbihari2881]

Mam U r teaching style is very good

[@ShivamSharma-lr2lr]

Thank you so much mam🙏🙏

[@IITian-NITian_0305]

Great mam.....

[@karthikrangaraju9421]

Why people don't explain the intuition behind problems? :( Can you explain WHY we take value just from above cell vs taking value from the delta????

[@ASHISHKUMARJHASONGS]

Mam as per your formula sum-A[i] , when sum=8 and arr[i]=7 --> sum-A[i]=1 and in above row A[1]=0 then how could you can write 1 there, please explain mam

[@amritpalsingh7262]

Great video👌😍, plz upload a series on Fibonacci heap and binomial heap I'll greatly appreciate it. Thanks 🙏

[@InderjitSingh-sh9ve]

Kitho veer g tusi

[@ashwanikumarsinha6350]

thanks

[@maheshlangote5436]

Thank you mam

[@basic_theory439]

first of all thank you very much for your explanation ,but small suggestion instead of directly hitting the solution kindly try to explain the logic behind that i.e why we are following Dp approach to solve this why Backtracking is not good. IT's like How we can solve this question??? And your answer is DP. But Y?

[@JennyslecturesCSIT]

Actually I have discussed the need of DP in one of my videos... U can check out the playlist Dynamic Programming..

[@ritvikraj8384]

can you give the link of the video in which you have calculated the subset of thhe sum.

[@lapujain]

what if the asked weight is too large like 100 or something, then we need to prepare a table for that. Not sure if DP should be used here.

[@sonurathod9551]

it was such a great video mam.Can you make videos on Greedy Algorithms??

[@zalatanibrah1803]

please make a video of how to find a subset thank you..

[@sargun_narula]

Use backtracking .. go back from the last column last row 1 and note down the row numbers as you proceed back .. you will get the subset

[@harrietobwogo720]

Hey Jenny this approach works if your array has only positive integers..what happens in the case of negative integers being in your list?

[@CodingWithPrakash_]

good question

[@princesoni4871]

nice explanation mam

[@prakhersrivastava2589]

Hello Riya , teaching very good

[@karanb2067]

ma'am please make a video on square root decomposition

[@mr68clubshorts]

THE İMPLEMENTATİON İS NOT CORRECT SİNCE A[i][j-A[i]] part is the reason of array index out of exception error but the explanation is correct the easiest way of implementtaion of this problem is recursive

[@bhogeswarasaikumar6351]

How to find those subsets?

[@sujithns5033]

Thanks for explanation. Can you please tell how to arrive at this solution. In dp, each and every problems seem to be solved differently. It would be helpful if you can explain that. Thanks

[@dr.nehajain1366]

Awesome

[@ekanshgaming5854]

Excellent Explanation. You are requested to use better quality of marker

[@dhawanrishab]

Hello, thanks a lot for the explanation. Just wanted to know why are all elements set to true for sum 0.

[@blackscreenm4662]

Cute mam,,cute explanation.. Love u mam.

[@memd777]

is it necessary that the Array A = 2,3,5,7,10 needs to be sorted for this to work?

[@ramakrishna-jk2jl]

No need, it will work with unsorted array as well.

[@kattelanithyasri7727]

how to print those subsets, please help

[@tushargupta2009]

Mam please upload more problems on dynamic Programming

[@universalstarcpu9522]

If the sum value is high it will be very complex to solve in dp . Is it any other method better than dp in that case?

[@diveshrajput572]

Mam, what is the time and space complexity of this algo?

[@moustafaali3555]

great but I did not understand how the sum can be equal to zero (first column) if I select A[i] at minute 6:30.

[@nadeemmansuri6414]

Mam please make the part two of the subset sum problem.

[@nagarjuna119]

core logic is not explained, why you go to upper cell, go back and check in different for value ?

[@muskanjindal2921]

mam how can we include the element when sum is 0

[@jrseinc]

very good explination. I have one question: Is it necessary that the set should be in increasing order for creating DP table?

[@thepenguineterror]

Yes otherwise the maximum sum will yhe sum of all positive number in the array

[@ankitamittal2618]

can u plz explain why u write 1 in column having value 0 ? what i understand is if we write 1 means we can make a subset and by having subset with value 2 or other, sum will not be 0. plz explain it

[@biswajitsahu7565]

mam,Where is the 2nd part!¿

[@AnandKumar-ro1yd]

Could you make more videos on problem solving and Dynamic problem

[@ivandrofly]

Why we need to row-1? Why not taking from current row? The value for row is already computed

[@kishanpandey5219]

If the sum is given 50 then .....will these tables still be feasible?

[@maheshpatil-pf2fd]

does the element of the should be return in sorted manner

[@ramakrishna-jk2jl]

No need, it will work with unsorted array as well.

[@singhscribe7450]

kindly mention the error in the table's last row and column where it shall be 0. If I am wrong, please let me know.

[@nagavenkataprakash4837]

Mam please make videos on oops concepts in Java

[@chandanbk114]

is this method using back tracking ?

[@thepenguineterror]

Plzz make more videos on DP

[@kunjeyan_5875]

Very nice explanation.. Loved it... But Ma'am, please explain why we are going to one cell back and then subtracting the value of i and getting the value of that cell (if the value in previous cell is 0) and if it is 1 we directly copy 1....please explain the logic behind this.

[@HXYZZZ]

you are targeting to get sum listed on top row. when your cell value is [left column] less than sum you are looking for, you are going back and see whether that difference can be achieved, by looking at that cell [the sum value listed in the top]

[@sachink.s838]

mam plz explain print all subset

[@Charlie-jx6mv]

Divide and conquer leads dividing main problem in to subproblems...

[@riteshchauhan0027]

Can you solve it with State space tree

[@aswadkakumani7379]

can you explain me how to solve any problem by using dynamic programming ..

[@balajee41]

Will it work if the sum is odd number? I wrote code on my own based on your explanation. It is not working if the sum is odd number.

[@SOURAVKUMAR-ps4zr]

Mam please give me an example of back-tracking

[@JennyslecturesCSIT]

check my video about it

[@young_age_designer1493]

Mam can you do video on subset program

[@prashantkumar2963]

how does it work?

[@greninjadp2564]

mam particular subset second vedios plz

[@GauravSingh-fy7do]

Nic

[@Akz77977]

24:41 , it will be A [ i - 1 ] [ j - A (i - 1) ] = 1

[@ashishdaniel169]

it is [i-1] in the first block because we are considering the previous row.. but when we are subtracting j-A(i) we are subtracting A(i) from the current row.. So j-A(i) is correct

[@bharatjoshi1473]

jenny the video is very help full about what we have to do , but it doesn't speaks any anything about Why we are doing it eg at 8:56 it says we have to do sum- A[i] but its not very clear why we are doing it why not Sum- A[j] or A[i]-A[j] ?

[@infotainment7123]

HOW TO WRITE CODE FOR IT?

[@thiraviamnatarajan5903]

Mam plz put queen problem

[@yatri6329]

What if array is not sorted

[@Pkhanwal]

Hello mam.. Is this solve by using backtracking

[@bhaskarbhasku2921]

Yes you can

[@selva140]

why you choose other elem for the sum=0

[@harshittiwari2281]

Mam what if the we have given sum like 245

[@Ayush_45_]

How to add 50 lines??

[@retrogame3138]

please upload hd video quality

[@crazydrifter13]

Mam, please avoid uploading in just 360p. It might appear fine now but people would hit dislike on your Good content when era of 5g and 4K arrives. Think long term for your channel.

[@gauransh18]

how to calculate subset you said you'll make a video its been 3 years

[@Historicalfacts60]

Mam u are looking gorgious

[@jayantgoel001]

Ma'am at @20:15 u said there will be another video of subset problem Can u please give link for the same Thank u in advance

[@nainaagrawal8314]

Next video link plss..

[@yashwinkolangi524]

Mam I guess in the place A[i]=3 and sum(j) =4 should be 1 😅

[@kedarmuley4142]

Ma'am second video???

[@thinkimagine6445]

so cute

[@yobro7051]

can u please provide the code

[@CodingWithPrakash_]

kzbin.info/www/bejne/m5vVZKugbZmnlbM

[@shubham8835]

no one explains why we are going backwards and simply copying values.. we are not here to mug things up

[@chitranshkulshrestha485]

Explanation is good but this is not a right way to teach DP. First we need to understand the recursive logic and when the recursive logic is developed then only we can made a DP solution. Video like this did not include basics of DP and no can solve questions of DP directly by making a table. If you do not know which problem is overlapping then how you can do so.