Subsets of an array 😰 | Inclusion exclusion | Decoding recursion | Nishant Chahar | Ep-5
Subsets of an array 😰 | Inclusion exclusion | Decoding recursion | Nishant Chahar | Ep-5
In this video, we will see how to find the subsets of an array using recursion. It is very similar to the subsequence problem which we solved in the last lecture. So watch that lecture before starting out this one.
Subset problem: https://practice.geeksforgeeks.org/pr…
You can use my code NISHANT to get 15% Off on all GFG courses.
✨ Important Links ✨
- Don’t Click Here: https://bit.ly/3afmPha
- Telegram Link: https://t.me/codeIn10byNishant
- Github Repo Link: https://github.com/chaharnishant11/Co…
✨ Hashtags ✨
#NishantChahar #Microsoft #DSA #Recursion #FAANG #NSIT #NSUT #engineering #internship #college
✨tags ✨
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn Operating systems
where to learn dbms
where to learn oops
where to learn computer networks
where to learn low level design
where to learn cs fundamentals
Sanchit jain
Gaurav sen
Gate smashers
Placement guide
How to start programming
where to learn cpp
where to learn python
where to learn javascript
where to learn java
Placement guide
Nishant Chahar Placement Guide
languages to learn
resources to learn data structures
Projects development
AR/VR
Blockchain Machine learning
Deep Learning
Software developer engineer ,
Side projects ,
Importance of side projects ,
Machine Learning Engineer,
How to become a machine learning engineer ,
Associate engineer
Data structures Algorithms
College Life, College, Memories
Fun Fests Chill Enjoy
IITD Mood indigo rendezvous IIT
NSUT Moksha DTU Engifest
Bits Bitsgoa
Namaste Javascript
Namaste Javascript Akshay Saini
Apna college
Apna college c++
apna college DSA
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn programming
how to start coding
where to learn coding
where to learn DSA
resources to learn programming
how to crack amazon
how to crack placement
blockchain
what is blockchain
blockchain technology
blockchain technology explained
blockchain explained
blockchain technology in hindi
web development roadmap
roadmap to learn web development
android development roadmap
MERN stack roadmap
machine learning roadmap
roadmap to learn machine learning
roadmap for deep learning
roadmap for 2nd years
roadmap for opensource
roadmap for ios development
roadmap for deep learning
roadmap to learn DSA
Content
0 -> Hi guys welcome to code in 10
2.113 -> I am Nishant
3.385 -> And in today's video we gonna talk about a problem named subset
5.87 -> Now what is this problem
8.123 -> It is very similar to the problem that we did in last video
10.726 -> Whose names were subsequences of a string
12.084 -> In this also we are going to do the same thing
14.285 -> inclusion or exclusion and take and not take the thing
17.48 -> We are going to do the same
18.952 -> Okay
19.783 -> Whoever hasn't watched the last video, do watch it
22.131 -> With that your understanding will be very nice
24.366 -> You will understand what we have done in this
26.6 -> Now lets understand a little bit
28.82 -> Lets make tree and recursive tree
31.144 -> Then we will come back to this code
32.303 -> I want to tell you one thing
34.22 -> all these questions that we are doing
35.472 -> All these are also solved with DP
37.417 -> With dynamic programming
38.8 -> When you will submit these on any online platform
41.48 -> So that will show
42.941 -> This is because
44.395 -> These are questions of Dynamic programming
47.622 -> And you can apply DPP in all of these
50.434 -> By applying DP, your time complexity becomes 2 raise to the power n square from 2 raise to the power n
54.52 -> We will talk about time complexity later
57.115 -> But yes understand there is a lot of difference
59.067 ->
60.234 -> We studied till now that what is recursion
62.687 -> Same 3 conditions
64.442 -> 1, 2 and 3
66.386 -> Base case, we are revising these in all the videos
72.121 -> So this is the same thing
73.88 -> Whoever is not understanding
75.682 -> Watch previous videos
77.116 -> You will understand
77.881 -> What we did in last video
79.429 -> We were finding subsequences
80.683 -> And I told you the definition of subsequence and subset in that video
84.43 -> You can watch it
85.942 -> If you didn't understand. Lets not repeat again
87.758 -> Because we gonna make crispy video in 10 minutes
89.847 -> So watch last one for better understanding
92.685 -> Watch the series from the starting, you will understand nicely
94.822 -> Okay
95.997 -> Now what is the scene in it
97.704 -> You are given an array
99.494 -> In which 1,2,3 are elements
101.69 -> Now you have to tell its all subsets
104.459 -> What exactly is subset
106.476 -> Lets tell a little bit
107.544 -> Subset is
109.158 -> If we will take current element or not
111.306 -> After that leaving that or taking that, all the small small subsets that are making
115.076 -> Small small sets are making
116.448 -> So lets start solving from recursion
118.735 -> In this we have to do that same take and not take thing
122.511 -> Currently we are at this element
124.487 -> Okay
125.283 -> Now lets make 2 arrays in it
127.042 -> This is temporary array
129.344 -> And with it, we have an index i
131.889 -> Okay
132.654 -> index i's value is starting from 0
134.819 -> Now we said lets take 1 once
138.608 -> It will come in take
139.926 -> 1, 2,3
142.43 -> elements. Here i become
145.191 -> 1
145.89 -> We incremented i
147.088 -> And 1 has been included in our current subset
150.163 -> Next we said lets do not take
152.944 -> i become 1
154.26 -> it will be 1, 2,3
156.524 -> Okay
159.155 -> and the subset is still empty
161.026 -> Next what we did
163.005 -> Next we did the same thing
165.103 -> We did take once and not take once
166.91 -> Means inclusion , exclusion
168.841 -> Inclusion, exclusion
169.872 -> We have to do this
170.836 -> Add once and do not add once
172.514 -> Add once and do not add once
173.728 -> All of your problems of subsequences and subsets gets solved
177.131 -> It is simple formula
179.374 -> Wherever you want to find subsets
180.989 -> Subsets sum to k
182.185 -> Subsequence same as this subsequence
184.911 -> We have to do inclusion and exclusion in all the problems of this type
188.507 -> Okay we will do take and not take in this again
190.522 -> We did 2 here and done take here
192.718 -> So our array was 1, 2,3
195.348 -> If we did take it, then it came 1, 2
197.055 -> Similarly we did 'not take'
199.12 -> it became 2
200.199 -> This remained same array
202.005 -> This one
203.391 -> And 1 remained here
205.289 -> Similarly what we did here
207.141 -> Once take and once not take
208.101 -> Okay
209.207 -> Take not take
210.702 -> So we came to 2 here
212.073 -> So we updated i =2
215.51 -> Array remained as it was
217.342 -> In subset, 2 has added here
219.3 -> Okay
220.332 -> Again we have come to i =2 here
222.347 -> Here our array will be 1,2, 3
225.33 -> It will be 1, 2,3
227.436 -> This remained empty again
228.911 -> Because there was not take in it
230.627 -> Similarly we will come here
232.415 -> i has become 3
234.101 -> What we did before having i = 3
236.412 -> We had reached at 2 here, so we included 3
239.479 -> 1, 2,3
241.78 -> And we didn't included in it, so it became 1, 2
245.086 -> Similarly we came here
247.086 -> In 1 , we did the third element as 1, 3 once
251.178 -> and one time we didn't do
253.311 -> So only 1 came here
254.397 -> And in all of these the value of i is 3
256.324 -> Remember this altogether
258.178 -> We came again here
259.898 -> In this , take and not take
261.23 -> it became 2, 3
262.239 -> And we did 'not take' so it became 2
264.039 -> Similarly in this take and not take
265.512 -> This became 3
266.726 -> And this remained 3
268.165 -> So now you will see
269.658 -> 1,2,3 came
271.221 -> 1, 2 came
271.935 -> 1, 3 came
272.839 -> 1 came
273.418 -> 2, 3 came
274.482 -> 2 came, 3 came
275.167 -> So in this also, same 8 cases created
277.707 -> It is same because number of elements will be same
280.005 -> Because that is 2 raise to the power n
281.377 -> Now why it is 2 raise to the power n because we have 2 choices
285.515 -> Either we take it or not take it
288.744 -> So that is 2 into 2 into 2
290.79 -> Become all of our options
292.418 -> As soon as we will move further in these
294.137 -> So this i = 4
295.525 -> If there were 4 elements
297.026 -> So it will reach to 2 raise to the power 4
298.878 -> Okay
299.546 -> 16 subsequences will be making
301.943 -> And in this way it keeps increasing
303.838 -> And many times what happens, numbers remains same
306.379 -> Many times you will get this question that
307.522 -> in this array, there is 1, 1,2
310.993 -> So how many unique subsequences does it have
314.576 -> Or subsets
315.945 -> Tell that
316.424 -> Now for unique subset , you will have to use set or map
319.398 -> You will have to check if this is added already or not
321.401 -> So these are small small variations in these questions
324.186 -> So I think you have understood it
326.227 -> Lets code it now
327.871 -> And with code we will dry run it again
329.81 -> Then you will understand it more better
331.061 -> Okay so lets start
332.899 -> We will solve it nicely
334.219 -> Now what we do here lets create a global variable here
336.831 -> We will tell later about global vs local
339.114 -> Global just means that any function can access it
342.218 -> Now we will make a helper function
344.115 -> Okay
345.572 -> In that we will have a vector
347.821 -> After that we will have a temporary vector
355.387 -> After that we will have index
357.795 -> Okay
359.524 -> In this base case was same as that was of last time
361.516 -> The base case is same. If value of i becomes equal to a.size
365.784 -> So what we do
368.639 -> We will push back inn answer
372.374 -> temp
374.723 -> Means whatever that is present in temporary array
376.589 -> Put that in answer
377.893 -> And we will return from here
379.35 -> This became our base case
380.655 -> After this we will first do include
383.279 -> After that we will do exclude
384.162 -> So what we will do to include
385.793 -> we will push back in temp
387.609 -> Those who are not understanding pushback
390.088 -> There is a function in vector
391.44 -> From which you can add a thing at the end of a vector
394.349 -> Okay
394.842 -> Vector is a type of array
396.141 -> Vector is a dynamic array
397.443 -> We will study in STL later
399.092 -> We will make a basic series of C++ STL
402.186 -> We will clear all of your doubts in that
403.638 -> Do not worry
404.308 -> But those who do not know
405.741 -> For now consider, it is of a vector type
407.931 -> An array type
408.633 -> In which we can directly add elements from the back side
410.359 -> We added A[I] in that
413.735 -> Now what we will do
415.377 -> WE will call the helper
416.258 -> Here we will include this
418.003 -> We will say our A, temp, index i + 1
425.122 -> Similarly pop back means
427.546 -> That remove from back
430.623 -> We will pop back again
433.095 -> We excluded this time
435.635 -> In inclusion and exclusion
436.8 -> And did this i+1
439.673 -> And we returned from here
441.529 -> Now what we will do here
444.28 -> We will make our temporary vector
447.308 -> Okay
448.904 -> Then we will call the helper
451.534 -> We will pass A, temp, 0 in this
456.789 -> And we will return here
458.076 -> Answer
459.349 -> Okay
460.316 -> This is our code
461.384 -> Lets compile run this once
462.862 -> Okay
465.167 -> This is showing output difference because
467.806 -> It needs sorted
468.694 -> So lets use inbuilt sort function here
473.264 -> What happens with sort function
476.439 -> That will give us in the sort order
478.3 -> And our expected and this become same
482.386 -> Lets submit this
483.555 -> And this will be submitted
486.177 -> Okay
489.326 -> Now lets understand this by dry running it
491.196 -> So we had A as 1,2,3
493.98 -> Okay
495.712 -> Our temporary is empty for now
497.2 -> And our index is 0
498.707 -> Okay. We came here
500.115 -> We checked if the value of 0 is equal to 3, no it is not
502.924 -> So we will not go inside it
504.173 -> We will go to temp
505.249 -> in temp, it will say out A[i]
506.715 -> A[i] is 1
507.909 -> We put 1 in this''
509.558 -> Okay
510.803 -> So it will say, put A[i]. What was our A[I], it was 1
515.198 -> We put 1 in this
516.273 -> So here 1 came
517.93 -> Right
518.705 -> After this it said
520.241 -> After putting recursion as 1
521.645 -> Call the recursion and go back above
523.405 -> Then we will check. We did value of i as 2
525.652 -> Okay
527.161 -> After doing this, we did value of i as 1 again
529.187 -> After doing 1, same thing came
531.238 -> We saw here 1 is not equal to 3
532.47 -> Okay
533.241 -> We had 0,1,2
535.459 -> We added 2 , it became 3
536.5 -> After adding 2, it became 1,2,3
538.321 -> And we did i as 3
539.751 -> From 3 it again went above
541.351 -> It checked
542.247 -> That if the value of 3 is equal to 3?
544.487 -> Yes
545.468 -> So it came here
546.206 -> It pushed back in answer
547.247 -> What we pushed back in answer 1,2,3 subset
550.453 -> And returned
551.523 -> 3 reached here after returning from here
553.177 -> After reaching here, what it did, it pop back
555.584 -> By doing pop back, the 3 that we added in it , removed
557.775 -> After adding 3, it again called
559.209 -> So 1,2 came
560.226 -> 1,2 came and the value of i became 3 again
562.419 -> if the value of i became 3, then it checked again
564.223 -> If the value of 3 is equal to 3
565.556 -> The value of 3 is equal to 3
566.555 -> It again pushed back
567.893 -> So we added this element also
569.824 -> Similarly
571.132 -> We went again
571.883 -> We went again from here
572.9 -> Our i=2 completed
574.485 -> It sent here, then it sent here
575.995 -> we came i =1
577.234 -> it said go back
578.526 -> before coming to 1, it pop back
580.346 -> So that we added here
582.247 -> 1,2
583.097 -> we removed 2 from 1,2
584.547 -> So only 1,1 left
585.368 -> So when you will do same thing again
587.417 -> Try doing dry run
588.976 -> Your output will be same
590.77 -> Other than this you can take one or two more examples
592.656 -> You can see our code has been submitted
595.246 -> So this was the question from which we have found all the subsets from an array
598.642 -> There are variations in this of doing print and all
601.439 -> And one more variation is also there of sum one
603.031 -> That we gonna study in next video
604.863 -> So thank you so much for watching this video
606.535 -> And keep making your love and support like this
609.269 -> Let's meet in another video
610.078 -> Till then bye
Source: https://www.youtube.com/watch?v=iqKwK_o93Gw