- 1 day ago
Transcript
00:00In the main function, I already made a string which is abc, now I will make a function of public
00:04static void find subsets
00:08In the find subsets, one will come to my string, the other will come to which I will store my
00:14answer, i.e. I will store my subset
00:16Besides, I can take another integer, what is this integer? It is my index
00:21I am asking which letter, which character I am asking if I want to enter my subset or not
00:28The index is showing me I
00:31Now, I have to do two steps
00:33The first step is my base case
00:36The second step is my recursion
00:39The first step is my recursion
00:40The first step is my recursion
00:42If my character says yes to enter the subset
00:46This is the yes
00:50The second step is my recursion
00:51You will know that backtracking is all about choices
00:55I mean, any character or element
00:57Which we can take the choices
00:58As much as we can take the choices
01:00There will be possible solutions
01:01When there are choices, there will be backtracking in maximum cases
01:07If I have taken the yes
01:09What will I do?
01:10I will call find subsets
01:11I have a string
01:13My i plus one
01:15If I have taken the answer
01:15What will I do?
01:16I will add
01:19str.character at i
01:23This is my yes
01:26If I have no
01:27If I have no
01:27What will I do?
01:29I will call find subsets
01:31But the answer is the same
01:34In this case
01:35I have no answer
01:39In the case
01:40What would I do?
01:41In the base case
01:42In the base case
01:42The value of the string
01:44Is equal to the length of the string
01:45That means
01:45I have given the choice
01:47What will I do?
01:48I will print my answer
01:50And I will return
01:52So only for my find subsets
01:56What will I do in this function
01:57What will I do in this function?
01:57In this function
01:58My base case will hit
02:00When my index
02:01Is equal to my string
02:02There will be my answer
02:04I will print
02:05Now
02:06As I am going up
02:06As I am going up
02:07To take the yes
02:07To take the choices
02:09The character
02:09The index
02:11Which is in the string
02:12That will add
02:14If I have no
02:15To take the choice
02:16That will not add
02:16But every time
02:18I will return
02:19To the next level
02:20I will ask the next character
02:21To the next level
02:21I will ask the choice
02:22In the main function
02:23I have made a string
02:24Now I am going to call
02:26Find subsets
02:27In this string
02:28I will pass the answer
02:29In the beginning
02:30I will pass the empty string
02:33And I will pass the value
02:35As 0
02:35Let's do this
02:36Save
02:36Now Run
02:40Now I have these subsets
02:43I have analyzed
02:43Before
02:44ABC
02:45AB
02:45AC
02:48BC
02:49BC
02:50BC
02:50And last
02:50I will not see empty
02:51I will not see empty
02:52I will add another condition
02:55If
02:55If
02:56My answer
02:57.length
02:58If it is empty
02:59Then the answer's length
03:00will be 0
03:01I will print
03:02I will print
03:04NULL
03:06What will happen in the other cases
03:07In the other cases
03:09My answer will print
03:11So I will see
03:13From here
03:13I will execute it
03:16I will execute it
03:17I will execute it
03:18And the same choices
03:19Again
03:19In fact
03:20The order
03:21There is also
03:21That
03:22ABC
03:22Then
03:23AB
03:24Then
03:25AC
03:25Then
03:25A
03:26You will compare it
03:28The order
03:28We have written
03:29We have written
03:31Approach
03:31Find out
03:31Time
03:32Then
03:32ABC
03:32Then
03:33ABC
03:33Then
03:34ABC
03:58Then
03:58A
04:00B
04:00So
04:01Coding
04:02There is
04:03Logical explanation
04:04If
04:05I have made
04:06That logic
04:06In the paper pen
04:06Then
04:08It is very easy
04:10I have made a tree
04:12Logically
04:13And
04:13You will see
04:14In the code
04:14There are 5 lines
04:16In the recursive function
04:17So
04:18That
04:18Very beautiful
04:20I have written
04:21So
04:22Beautifully
04:23A tree
04:24Structure
04:24And
04:26Backtracking
04:27Recursion
04:27Internally
04:28Now
04:29What we will do
04:30A little
04:32Call stack
04:33Analyze
04:33So
04:34How do we analyze the call stack?
04:37What did I do?
04:38What did I do?
04:39I will analyze it
04:40A little
04:41What did I do?
04:42I passed the string
04:44As
04:44ABC
04:46My answer
04:47Was empty
04:48And I
04:48Passed
04:49Zero
04:50The first level
04:52I will come in
04:53Before
04:53I will see the base case
04:55If the condition
04:57Falls
04:57So
04:58I will go here
04:58The first choice
05:00In fact
05:01This line
05:02This line
05:03This line
05:04This line
05:04Was to go up
05:04And this line
05:06This line
05:07This line
05:07Was to go down
05:07This line
05:08This line
05:08This is my
05:10Yes
05:10This is my
05:14No
05:14If I am
05:15Yes
05:16What will happen?
05:17My find
05:18Subsets
05:19In my
05:20I value
05:210
05:21Now
05:22When I call the upper level
05:23I will send my answer
05:26As a
05:27Here
05:27My answer
05:28Was empty
05:28This line
05:30I will write my answer
05:31So
05:32The next level
05:33The next level
05:34The next level
05:34The next level
05:35I value
05:36I value
05:36I value
05:37What will happen?
05:39First character
05:41This is 0
05:42B1
05:43C2
05:44So
05:45A
05:45B
05:45What will happen?
05:46Yes
05:46The first choice
05:48You have to reference your code
05:49Here
05:49You have to reference your code
05:51Because this line is below
05:53This line is above
05:54This line is above
05:55This will be a little mistake
05:56You have to analyze it
05:58Then
05:59I have to select find
05:59Where I chose a
06:01And I have to choose a
06:03And I have to choose a
06:03And I have to choose a
06:04I have to choose a
06:05To the next level
06:08I gave the list
06:08To the next level
06:09Call
06:09I have to give a
06:11As a
06:12So
06:12As you can see
06:15I have to choose a
06:15This line is a
06:15I have to choose a
06:18From the other level
06:20I will see that my answer's length is 0 and that my answer's length is not 0, so I will
06:25print my answer.
06:26So my answer will print in the answer. I will print in the answer.
06:31Here I will print A, B, C. Now what I will do? I will print this.
06:35So I will return return here. So here I will backtrack.
06:39Backtrack and I went down a level. So my level is empty.
06:43As the level is empty, the answer will be removed from here.
06:47Why? Because in Java everything is passed by value.
06:51The answer, my string answer was on the upper level.
06:54Now there will not be changes on the upper level.
06:57Because those changes were passed by value.
07:00They were only with the upper level.
07:03Now the upper level, because the string doesn't become new.
07:06There will be no change in string.
07:08Because string is immutable.
07:12The first thing I have told in the chapter, strings are immutable.
07:16There will never change. If I change, it will become new.
07:18So the thing I have changed in the chapter, which I have added in the next character.
07:22That was a new string answer to this level.
07:26Now the level is removed, so the string answer also removed.
07:29So I have the previous answer, which is my A, B.
07:32Now as I came to this level, this is the call.
07:34Now the second call will be executed.
07:35I have no value choice.
07:38Now if I have no value choice here.
07:39If I have no value choice here, then I will go up here.
07:42And this is no value choice.
07:45Then I will call for I is equal to 3.
07:47Which will only be A, B.
07:48No, C will not be because it is no value choice.
07:50If I is equal to 3, then I will hit base case.
07:53Then I will hit base case.
07:54What will happen here?
07:55I will print my answer again.
07:56I will print my answer again.
07:57Now my answer is A, B.
08:00I will print it again.
08:03Now I will return again.
08:04Then what will happen again?
08:06Backtracking will be backtracking.
08:07So I will go back here and go up here.
08:10The upper call will be removed.
08:11The upper answer will also remove me.
08:13What will I do now?
08:14I will see again that my two calls will be removed.
08:17Here C will be yes and no.
08:20So I will backtrack again.
08:22I will come down one level.
08:23The upper level will be removed.
08:26The upper answer will also be removed.
08:29I will come down to this level.
08:30At this level, B was yes and no.
08:35I will no call.
08:37Now I will go up to one level.
08:38I will put FIND SUBSETS again and I will call.
08:41I is equal to 2.
08:42Now B is no and no.
08:45A has said yes and B has said no again.
08:47Now it will place one level again.
08:49For C.
08:50Before C is yes.
08:52I have FIND SUBSETS again.
08:54I will call 3.
08:55And now I have A and C
08:58B has taken no
08:59Where did B no choice?
09:01Where did B no choice?
09:02It was here
09:04This level B has taken no choice
09:07This level A
09:10Yes
09:10Here B has taken no choice
09:12Here C has taken yes
09:17Then here C added
09:18The level of I is equal to 3
09:21I is equal to 3
09:22I will print the answer
09:24I will print the answer
09:25What is the answer?
09:26What is the answer?
09:26The answer is AC
09:27So after that
09:28I will print AC
09:29I will print AC
09:30I will return
09:32As I will return
09:32This level will be removed
09:34This level will be removed
09:35This will be removed
09:36My answer will be removed
09:37So the whole call stack
09:39You have to complete complete
09:41And there are very few steps
09:42I have printed 3
09:44The rest are only 5 steps
09:46Which is almost easy
09:49So it is easy to analyze this call stack
09:52In fact
09:53We will analyze it
09:54We will analyze it
09:55We will also clear
09:56How is the recursion
09:57When we are going up
10:00This is my function calls
10:02When I backtrack
10:04Backtrack
10:04Backtrack
10:04Backtrack
10:06Backtrack
10:06Backtrack
10:06Backtrack
10:07Backtrack
10:22Backtrack
10:29The next step is
10:31That is
10:31because I didn't use any extra space so that will be big of n
10:34Now how did the time complexity big of n into 2 to the power n
10:38because I have total subsets
10:41Do I know that my total subsets
10:44If my string size is n
10:46they are equal to 2 to the power n
10:47and how much time takes out of one subset
10:51so how much time takes out of 2 to the power n
10:562 to the power n into n
10:59That is why this is my time complexity
11:01Now how do 2 to the power n subsets come from 2 to the power n
11:04because I have n elements
11:07I can call them n characters
11:09I can call them n characters
11:11If my string is a,b,c,d,ef,gh
11:14something something
11:14If there are n characters
11:17and each character has 2 choices
11:19So what can I say?
11:20The first character has 2 choices
11:22and this one has 2 choices
11:24and this one has 2 choices
11:26In this way we have n characters
11:28So what can I say?
11:30The total number of possible subsets
11:32can come or not
11:34This can come or not
11:35This can come or not
11:35This can come or not
11:36This can come or not
11:37This can come or not
11:51Damn or not
11:52And tym n timesどう
11:54do this While
11:56there are 2 to the power n I
11:57multiplied by n times How
12:00many subsets become now? Because
12:01we have 2 to the power n subsets I
12:03have 2 to the power n subsets The
12:03first thing I discussed was
12:05that When
12:05I have any lake n-size
12:07If there are n elements, the logic is here because every element, character, letter
12:16has two choices.
12:17So, to find out one subset, I have to ask each character if you want to come or not.
12:26If I have a, b, c, then I will ask if I want to come or not.
12:29If I have a, b, c, then I will ask if I want to come or not.
12:32When all the n characters will tell me that the choice is yes or no,
12:39then my final subset is formed.
12:41So, how much time is the subset in their form?
12:44How much is the string size? How much is the string size?
12:47It is equal to n.
12:48If I have a subset in a form, n is the time.
12:52I have to ask n characters if I want to come or not.
12:55So, 2 to the par n, i.e. how much time will it be?
12:59It will be 2 to the par n multiplied by n.
13:02So, in this simple way, I have calculated the time complexity.
13:06In fact, if we look at our recursion tree,
13:09how much time did the base case come from above?
13:12This is 1 step, this is 2 step, this is 3 step.
13:15And in 3 steps, I have come.
13:16I can say that I reach n steps in my base case.
13:20This means that in 1 subset is n steps.
13:23In 2 subset is n steps.
13:25In 3 subset is n steps.
13:26In 3 subset is n steps.
13:27In 4 subset is n steps.
13:29So, in this way, 2 to the par n into n steps.
13:32This will be my time complexity.
13:34And in 1 bar, there are total n levels.
13:38That is why space complexity is big .
13:40Now, in this question, I have used strings.
13:43But besides the strings, I had to calculate the answer.
13:46I had to use the string builder.
13:48So, I have to optimize this thing here.
13:50So, if I don't form strings every time,
13:52I can change the same object in the same object.
13:54You can try this to solve the string builder.
13:57But in that case, I have to add an extra step here.
14:00Which will be to my delete my character.
14:04Which I have added to the string builder,
14:06I will also have to remove the subset.
14:09I will also have to delete it.
14:11Because it will automatically delete it.
14:14So, you can explore it.
14:16You can try to solve this question from the string builder.
14:18If you want to take the answer from the string builder type.
14:22I hope that in this question,
14:24we will be clear logic, recursion tree, call stack,
14:27code and time complexity.
14:29Because this topic, which we have solved the whole question.
14:34This is a very basic form of backtracking.
14:38If we are clear,
14:39then we will be clear in the next question.
14:42Backtracking is not difficult.
14:44It is not difficult.
14:45In fact, it is very easy.
14:46If recursion, basics and divide and conquer clear,
14:49then backtracking will be very easy.