• 1 day ago
Transcript
00:00Next question, which we will talk about is findSubsets.
00:03I will give a string for which I will take out the subsets.
00:06Now, sets, which I don't know, set is a collection of objects,
00:09when many things happen and when we make a collection,
00:13we call set.
00:14Subset, which is small sets,
00:16so when we make small collections,
00:17we call subset.
00:19So, in this question, we will give a string,
00:21like this string is ABC.
00:23I will find out all the subsets
00:26and print them.
00:27So, I will print all the subsets.
00:29Like I will talk about ABC.
00:31In ABC, if I make a subset of characters,
00:35then I can make a subset of one size.
00:38First, I have only taken A,
00:40then I have only taken B,
00:41then I have only taken C,
00:43then I have also taken A with B,
00:44then I have also taken B with C,
00:46then I have also taken A with C,
00:47then I have also taken ABC.
00:49Besides, there is one other subset, which is empty set.
00:56I have not taken anyone.
00:57I had a choice in the collection,
00:59that I can take anyone in the set,
01:01or I cannot take any element.
01:03Now, what do I do?
01:04I have made a set,
01:05which I have not taken anyone.
01:07We call it NULL set.
01:09In math, we represent it as phi.
01:12This is my NULL set.
01:13So, if I count here,
01:15how many sets I have?
01:16I have sets here,
01:183,
01:193,
01:196,
01:20and 2,
01:208.
01:21So, the total subsets,
01:23the total subsets,
01:24the total subsets is basically,
01:25a small set,
01:26or a small set,
01:27so that is a subset.
01:29So, here I have 8 subsets.
01:32Now, I will share a small thing.
01:34If any string's length is equal to N,
01:38then the total subsets can be 2 to the par N subsets.
01:45Or, if I talk about my array,
01:47if I have N elements,
01:49I have an array that has N elements,
01:51and if I have N elements,
01:53then I have 2 to the par N.
01:56If I think I have some balls,
01:58I have different colors,
02:00and I want to make them subsets.
02:04So, if these are N balls,
02:05then I have 2 to the par N subsets.
02:08This is mathematically always true.
02:12And we will also see this.
02:13This is the fact.
02:14In this form,
02:15we are designing our recursion and backtracking.
02:20But,
02:21when you have N elements,
02:23how many subsets can be made?
02:25It can be 2 to the par N subsets.
02:28Now, we will make a recursion tree.
02:30After that, we will understand
02:31that we have 2 to the par N.
02:33And, if you have time complexity,
02:35it will be very much
02:36and it will grow.
02:37So, we will be clear
02:39that it is 2 to the par N.
02:41The recursion is also exponential.
02:44So, you will be able to relate a little bit,
02:46but we will not.
02:46We will understand it in detail.
02:48What is our approach
02:49if I want to find out
02:50with any string and subsets?
02:52If I start with my string,
02:54or with A, B, C,
02:55or with A, B, C,
03:03or with A, B, C,
03:16or with A, B, C,
03:22or with A, B, C,
03:23or to not to be the part of the subset.
03:26Now, if I give the same choice
03:28to my characters,
03:30then what will happen?
03:31First of all,
03:32let's say A.
03:34What choice has been made?
03:35A has made the choice of yes.
03:37That is,
03:37that is the part of my subset.
03:39I can imagine the subset
03:39as a box.
03:41This is my box
03:42which I collect my characters.
03:44So, A has already made the subset of my subset.
03:46Now, I have to ask who to ask?
03:48I have to ask B and C.
03:50Either A can be yes or no,
03:53or A can be no.
03:53If I say no,
03:54then my box,
03:55the subset of my collection,
03:56what is empty?
03:59What is left out?
04:00What is left out?
04:00Only B and C.
04:02I mean,
04:02A has a choice.
04:03Either it will come to my collection
04:04or it will not come to my collection.
04:07In one case,
04:08it will come to the collection.
04:09Then, I have to ask B and C.
04:11In one case,
04:12it will not come to the collection.
04:13Then, I will ask B and C.
04:15Now,
04:16when I reached this stage,
04:17I mean,
04:18A is in my collection.
04:20Then,
04:21who will I ask?
04:22I will ask B.
04:24Now,
04:24I will ask B.
04:25I will ask B.
04:27I will ask B.
04:28If B has a choice,
04:28either B will say yes,
04:30or B will say no.
04:32If B has said yes,
04:34then,
04:34how will I see my collection?
04:35A will also come to my collection,
04:38and B will also come to my collection.
04:38Now,
04:39I will ask C.
04:40I will ask C.
04:41Because A has already been in this collection,
04:43and B has also said yes.
04:45So,
04:45A,
04:45B has also been in my collection.
04:47Now,
04:47I will ask C.
04:48If B says no,
04:50then,
04:50what happened?
04:52Then,
04:52in this case,
04:53I will ask A.
04:55Now,
04:55I will ask C.
04:57So,
04:59I will ask C.
05:32I will ask C.
05:33A,
05:34I will ask C.
05:58So,
05:59I will ask C.
06:01A,
06:07I will ask C.
06:28I will ask C.
06:29So,
06:30what will I do?
06:30First of all,
06:31I will ask C.
06:32So,
06:33what will I do?
06:33What will I do?
06:34What will I do?
06:35I will ask A,
06:36I will ask C.
06:37But,
06:37B has already been here.
06:46What will I do?
06:48I will ask C.
06:49I will ask C.
06:49I will ask C.
06:50What will I do?
06:52What will I do?
06:52C will ask C.
06:54As I said C,
06:55I have another subset.
06:58Because,
06:58I will ask A.
07:02I will ask A.
07:02So,
07:02what will I do?
07:03I will ask A.
07:04I will ask A.
07:05I will have to calculate A.
07:08Now,
07:09I will go back.
07:09What will I do?
07:11Yes or No.
07:12I will ask C.
07:14So,
07:14I will go back to C.
07:16What will I do?
07:18That will be,
07:18Yes,
07:19I will take No.
07:21I will be not.
07:22I will go up one level.
07:25What will I do?
07:26A has got a choice.
07:28A has got a choice.
07:28A has got a choice.
07:29I will complete it and show it.
07:31A will take a whole.
07:33This is with no.
07:34Now,
07:34I have no choice to analyze.
07:36A has got a no choice.
07:37What will I do?
07:39The square will come out?
07:39My subcet will be gone.
07:40Now,
07:41I will have B.
07:43What will I do?
07:44B has got two choices.
07:45B can say yes,
07:46or no can say no.
07:48B has said yes, the subset will be only B. Now, it will save the answer for C.
07:56Now, C also asks what choice is. This can also be given two choices.
08:00It will be yes or no. As he said yes, I will give this step a little bit.
08:09As C said yes, my subset has become B, C.
08:15Now, if I have no choice, I will give this to B, C to print.
08:19So, here will be my 5th string, 5th subset will be no.
08:26As I said no, my subset will be only B.
08:30If I have no choice, I will give this to B.
08:35Now, here I have seen this choice, I will go back to this.
08:39If I have no choice, if I have no choice, if I have no choice,
08:44then what will happen? It will be an empty subset.
08:48In which there will not be A, because A had no choice,
08:51nor B had no choice, because B had no choice.
08:54So, what will we do in this subset?
08:55I will ask C.
08:57As I will ask C.
08:58As I will ask C, there will be two choices.
09:01One is yes and one is no.
09:04In which there will be yes, what will be no?
09:06In which there will be no.
09:07In which there will be no.
09:08In which there will be nothing.
09:09In which there will be no choice.
09:09This will be my empty subset.
09:11So, as C has said yes.
09:13In which there will be no choice.
09:15In which there will be no choice.
09:17In which there will be no choice.
09:18It will be null string.
09:20Either I can call null or empty.
09:22So, if I count as I will.
09:24How many subsets are coming?
09:26I have 8 subsets.
09:271, 2, 3, 4, 5, 6, 7 and 8.
09:31Which is the null one.
09:33Now, what I have processed.
09:35I will understand correctly.
09:37What did I do on every level?
09:38What did I do on every level?
09:40I asked my character.
09:42What is the choice?
09:43Either he can say yes in the subset.
09:46Or he can say no.
09:47Who asked from the beginning?
09:48In the beginning, I asked from I is equal to 0.
09:51I is equal to 0.
09:52I is equal to 0.
09:53Now, A has said yes.
09:55Now, I have asked from I is equal to 1.
09:58I is equal to 1.
09:59I is equal to 1.
10:01Now, I have asked from I is equal to 2.
10:05I have asked from I is equal to 2.
10:08I have asked from I is equal to 3.
10:10I have realized that my string is finished.
10:13Because there were elements in my string.
10:15So, I realized that all the characters have taken the choice.
10:18Now, I have to print the final subset.
10:20So, I have printed the ABC.
10:21After printing it, I will go back here.
10:24And I will analyze the C of no.
10:26And I will analyze the C of no.
10:28After these steps, this is actually backtracking.
10:30I have returned.
10:31My recursion has gone.
10:33When I return with recursion,
10:35I will ask backtracking,
10:36which we discussed in the last lecture.
10:38It will be my backtracking step.
10:40And I will take the C of no.
10:42Then, C will remove the No,
10:43So, I will print it.
10:45I will print it.
10:46And here from B.
10:46I will return with B to B.
10:49And here from B will I return.
10:49So, this will be my backtracking.
10:51Then, B will analyze the B.
10:52So, we will analyze the B and C, then we will ask C, then A and C.
10:59So, what did AC? I have backtracked.
11:03Backtracked and I came to this level again.
11:06What is this way?
11:08I am going to grow a problem.
11:12When I reached a solution, I will backtrack.
11:16Then I will reach a other solution and then I will backtrack.
11:18Then I will reach a third solution and then I will backtrack.
11:20Then I will reach a third solution and then I will reach a third solution.
11:25Then I will reach a third solution and then I will reach a third solution.
11:30So, my recursion tree will become my recursion tree using backtracking.
11:34So, after reaching every solution, I am going to a little back.
11:38Now, if I analyze it, what do I have every time?
11:41If I have a recursive function, I will name this function.
11:47FindSubsets.
11:48FindSubsets function, if I have a string.
11:50So, what I can say is that my final subset, I would store another string in the subset or answer.
11:58My answer string is empty.
12:01This is my box.
12:02I can call my answer string.
12:04In the beginning, I have only added A, A, B and A, C.
12:07So, at every level, I have two choices.
12:10One choice is that I will add in the answer.
12:14Who will I add?
12:15I will add my character of I.
12:17String.carat.
12:19I will add.
12:21The second choice is that I will not add anything in the answer.
12:24I will not add anything in the answer.
12:25I will leave it empty.
12:27I will leave it empty.
12:27So, I will take these two choices.
12:29One time, my character will add.
12:31One time, my character will not add.
12:33And, like I will reach the base case.
12:34What does the base case mean?
12:36The base case means that when all my characters are finished.
12:38All characters are finished.
12:40What do I want to do in the base case?
12:41What do I want to do in the base case?
12:42I will print my answer.
12:44If I talk about this whole recursion,
12:46This is my base case.
12:49This is my base case.
12:50This is my base case.
12:52This is my base case.
12:52This is my base case.
12:53These are all my subsets.
12:56These are all my base cases printed.
12:58When I finally reached here.
13:01Let's see this code.
13:02Let's see this code.