"Don't even think about the recursion that's happening. Just imagine you are calling a different, working function" - Best explanation ever. This line lit the lightbulb in my head. Thanks :)
sir video tutorials are common nowadays but ur videos are unique because u r speaking about how to approach the problem rather than giving a question and solvng it so do more of such videos on how to approach the problem in a different manner
I haven't finished the video but right now, I keep thinking about all of the different paths that you can go down, keep thinking about the recursion... and then once you return you go up the path until you can make another decision based off of where you end up but it's just very... complex when you think about it... I mean the base cases do make a lot of sense but the way I'm thinking about it right now is too hard to grasp, it's almost mind bending.
I was looking for videos on backtracking.. i did not want to waste my time.. so i scrolled many times before i found a video title that talked about "thinking" about backtracking.. well done sir!!
Thank you so much for creating this video - you explained recursive backtracking in a very easy to understand way, as well as showing the relevant code!
You should be a teacher. The way you lay out your thought process in a simple and detailed manner, allows us to replicate that thought process on our own and gain a deep understanding.
dude - this was the video that actually unlocked the concept of backtracking for me, in a way that I can now start to understand problems going forward. Huge props. I will have to check out your library of videos and i'm not sure if you're still making them but if so I'd love to hear you explain some more concepts. Thanks for making the effort, its much appreciated
Here's how I think of it: Backtracking = recursive brute-force Backtracking is a type of recursion, that's meant for brute-force It's called "backtracking" because when a wrong answer is found, the program has to return back to each recursive call until some original call is made, and then try another possible answer You say backtracking can be iterative rather than recursive, but I believe most people refer to it as recursive, so it believe it was defined to be recursive Top-down dynamic programming = memoized backtracking Top-down dynamic programming = memoized recursion, as well, which includes memoized backtracking
One thing to note is that you only need to keep track of visited because there may be cycles. In his example there are no cycles, so the maze is essentially a tree. There is no possibility of hitting a previously visited node. However, if there was no wall between 2 and 5, keeping track of visited becomes important. I mention this because someone might be looking at the maze and thinking they don't actually need visited, but in the general case, you do.
True and a good point. And this is true of a lot of search problems; if there are no cycles, you can get away with just using a stack so you can backtrack, but if there are cycles, you need to a way to track visited nodes.
i have a question. how could u make the while loop with conditions iter and foundoutlet terminates because i didn't see anything to trigger its termination here?
Really great video, thanks for giving a non-recursive solution, it helps putting things back in perspective. I'm wondering if this can apply to problems that search for a min/max value? For example, the classic "bag" problem which is traditionally solved using more "combinatory-oriented" approaches. (bag can carry at most N kilos and you have many items worth different values and weights, and you want to find the combination of a minimum items that are worth the maximum amount of gold)
Thanks! Yes, you could use recursion to solve that problem, which I know as the knapsack problem. The function could have two parameters: a maximum weight (maxWeight), and a list or other structure with all the items (AllItems), each with a weight and value. Also suppose there is an easy way to make a copy of that list without its first item (AllButFirst). The logic would then be, which of these has greater value? A. the recursive call with (maxWeight, AllButFirst) B. the recursive call with (maxWeight - weight of first item in AllItems, AllButFirst) + value of the first item in AllItems The recursion would stop when AllItems has zero items. Something like that.
If you want to know what is happening with recursive backtracking each possible route (assuming the maze is solvable) is made out after each step you take. The program knows all the results before it actually prints back anything to you! Like a teacher grading a paper, you don't know the grade until they tell you. If you step into a wall the code says welp I am done time to free up some memory and undos the step that led you to the wall. Why? Because programming languages keep track of things (like each step in a maze) using a stack of method calls. Once you walk into the brick wall in the maze the program says okay nothing to do here lets pop off all our steps. Oh wait now I can go this way (0-3) Obviously just imagining you are calling a different, working function is a much simpler way to think about it.😅
#cons : Type your program while you're explaining otherwise it will be difficult to go through. Explain the concept before hand. Thanks for your Video👍
Does the code without recursion actually works?? I've tried to replicate it in ruby but I have found some roadblocks. Probably due to the use of List here... How exactly do the begin() and end() methods work?
The code all works. I've done very little programming in Ruby, so I can't help you there. But I can explain how a list iterator works. Let me start by analogy and see if this helps. Imagine that we declared an array myArray and the constant SIZE specified how many members were in the array. So myArray[0] through myArray[SIZE - 1]. Then begin() would be like setting a variable called arrayPosition to 0, the first index of an array. And end() would give you SIZE, so if arrayPosition == SIZE it means you have advanced arrayPosition off the end of the array. (I think in Ruby you can legally reference elements outside the original range of the array, but you get the idea). Because you can dynamically add elements to arrays in Ruby I think the code should be translatable from C++ lists to Ruby arrays. Let me know if you have any more specific problems and I'll try to help.
That's the kind of problem where "backtracking" would be implicit and hard to see as such. Let's say you wanted to produce all the permutations of the letters A through Z. Let's suppose the language you are working in has a string library with functions or methods that 1) add a character to the end of a string 2) determine the length of a string 3) gets you the character at a certain position and 4) tells you if a character is in a string. Then we could write a recursive function to output all permutations of A through Z as follows. Our function has one parameter called PartialPermute. The code in the function would do this: -- if PartialPermute has 26 characters, output it and end the function (i.e., return) -- otherwise, loop a variable called Letter from 'A' to 'Z' ---- inside the loop, check to see if Letter is not already in the string PartialPermute ------- if not, copy PartialPermute to TempString, append Letter to TempString, and recursively call this function, passing TempString as the argument That's pretty much it. Again, backtracking here is implicit. You could make the backtracking more visible by appending Letter directly to PartialPermutre instead of using TempString, and then you would have to strip the last latter off PartialPermute after the recursive call, a kind of backtracking. Of course, if you wanted to store the results instead of display them or make a more general permutation function this would have to be expanded a bit but that's the basic idea.
Thank you! I have researched a little bit on the subject and your video was the best explanation of even an indirect example of the problem I had. Well done!
I have a doubt,this library that includes "push_back", "empty", "insert", how can i implement in C? (don't get angry please, i'm still learning, but in C, not C++)
Dude, In the 1st solution you have used the (!) operator with foundOutlet(line 26) which is declared false. Your program will never enter the second loop. Remove (!) then the program will work just fine. In the first program when I'm printing iter at line 25 and line 27(say) i.e before and after the second while loop its giving me {1,0,1,0,1,0,3,4,3,4} and {1,0,2,1,0,2,1,3,0,4,3,5,4,3,5,7,4,8} respectively. Im unable to understand how the iterator is moving.
um no that is wrong, the loop will execute as foundOutlet is set to false, and the second while loop only executes if this boolean value is set to false. if foundOut was set to true then the loop would not execute
I can try to answer that. Do you mean literally why it's part of the while loop condition? That loop exists to set foundOutlet to true if we find a connection from the current point to an unvisited point. We're not counting how many unvisited points we can reach, we only need to know if we can reach one, or not. So once we find an unvisited point (setting foundOutlet to true), we don't need to continue the loop further. That's why the !foundOutlet condition. Of course there would other ways of accomplishing the same thing. Let me know if this isn't what you meant.
Ha! For that you'll need a non-deterministic computer. You still don't make only right decisions, but because you make all possible decisions simultaneously, you can pick the one that ends up at the exit.
"Don't even think about the recursion that's happening. Just imagine you are calling a different, working function" - Best explanation ever. This line lit the lightbulb in my head. Thanks :)
This was amazing, thank you for also not jumping into recursion but instead showing this solution.
Hope everyone is having a great 2018 so far. This video's topic was viewer suggested. If you have an idea for a future video, let me know!
Dijkstra and belmanford shortest algorithm ...Can u explain us.practically
...
Sure, that sounds like a good topic. I'll add it to the list. Thanks for the suggestion!
sir video tutorials are common nowadays but ur videos are unique because u r speaking about how to approach the problem rather than giving a question and solvng it so do more of such videos on how to approach the problem in a different manner
Well done on the video!
Can you do it for python please
"Not think about the backtracking" - this literally changed my life :D So good!
This is one of the best explanations I've ever found. Thanks for making this video :)
Thanks for your comment. Glad you found it useful.
I haven't finished the video but right now, I keep thinking about all of the different paths that you can go down, keep thinking about the recursion... and then once you return you go up the path until you can make another decision based off of where you end up but it's just very... complex when you think about it... I mean the base cases do make a lot of sense but the way I'm thinking about it right now is too hard to grasp, it's almost mind bending.
I was looking for videos on backtracking.. i did not want to waste my time.. so i scrolled many times before i found a video title that talked about "thinking" about backtracking.. well done sir!!
Thank you so much for creating this video - you explained recursive backtracking in a very easy to understand way, as well as showing the relevant code!
that Robot analogy was amazing!
Thanks for the video
You should be a teacher. The way you lay out your thought process in a simple and detailed manner, allows us to replicate that thought process on our own and gain a deep understanding.
He is a teacher :))
Yeah, or he could make videos teaching. In a youtube channel or something like that.
He is a teacher, and one of the best I’ve had
dude - this was the video that actually unlocked the concept of backtracking for me, in a way that I can now start to understand problems going forward. Huge props. I will have to check out your library of videos and i'm not sure if you're still making them but if so I'd love to hear you explain some more concepts. Thanks for making the effort, its much appreciated
this is one of the best explanations I've ever seen. I wish you to keep going on to brush up more information
I need some serious help. I can understand how this works but I cant come up with a code by myself.
Same here!!!
Can you explain 8 queens problem. I found your explanation and reasoning very clear.
Could you show how the list sample_maze is being generated and called in main?
When I called the backtrack function sample_maze[9] is empty.
Thank you very much!! i dont know why you content underrated. keep making videos good luck!
Thank you sir for this wonderful series of videos ...
You're welcome! More on the way.
Best backtracking video I found on youtube.
You are amazing. You really made backtracking very simple.
Here's how I think of it:
Backtracking = recursive brute-force
Backtracking is a type of recursion, that's meant for brute-force
It's called "backtracking" because when a wrong answer is found, the program has to return back to each recursive call until some original call is made, and then try another possible answer
You say backtracking can be iterative rather than recursive, but I believe most people refer to it as recursive, so it believe it was defined to be recursive
Top-down dynamic programming = memoized backtracking
Top-down dynamic programming = memoized recursion, as well, which includes memoized backtracking
This algorithm help solve the last puzzle in building my spaceship. Thnx
Glad to help. Best wishes on your flight.
Thank you so much! I've learned new things from you.
Nice vid! What microphone are you using?
Was sent here by Sweigart's recursion book!
One thing to note is that you only need to keep track of visited because there may be cycles. In his example there are no cycles, so the maze is essentially a tree. There is no possibility of hitting a previously visited node. However, if there was no wall between 2 and 5, keeping track of visited becomes important. I mention this because someone might be looking at the maze and thinking they don't actually need visited, but in the general case, you do.
True and a good point. And this is true of a lot of search problems; if there are no cycles, you can get away with just using a stack so you can backtrack, but if there are cycles, you need to a way to track visited nodes.
This channel should create more content. I'm learning a lot.
Amazing explanation 🙏🏼
Glad you found it helpful, thanks!
Splendid explanation!
@vantonspraul, You have not used backtracking by removing last integer from the path in recursive solution. Are you sure it is working ?
really inspiring. I always got confused when I tried to think about backtracking in recursions, now I don't.
Best way to understand ...thanks
Thanks! Glad it was helpful.
Thanks man! Very well explained! Keep going!
Thank you, great video, iterative solution was very intuitive
i have a question. how could u make the while loop with conditions iter and foundoutlet terminates because i didn't see anything to trigger its termination here?
Really great video, thanks for giving a non-recursive solution, it helps putting things back in perspective.
I'm wondering if this can apply to problems that search for a min/max value? For example, the classic "bag" problem which is traditionally solved using more "combinatory-oriented" approaches. (bag can carry at most N kilos and you have many items worth different values and weights, and you want to find the combination of a minimum items that are worth the maximum amount of gold)
Thanks! Yes, you could use recursion to solve that problem, which I know as the knapsack problem. The function could have two parameters: a maximum weight (maxWeight), and a list or other structure with all the items (AllItems), each with a weight and value. Also suppose there is an easy way to make a copy of that list without its first item (AllButFirst). The logic would then be, which of these has greater value?
A. the recursive call with (maxWeight, AllButFirst)
B. the recursive call with (maxWeight - weight of first item in AllItems, AllButFirst) + value of the first item in AllItems
The recursion would stop when AllItems has zero items. Something like that.
wow! just wow! thank you sir!
Thank you for this amazing explanation
Nice video. May I also add that he sounds a lot like Kevin Spacey from House of cards...
Very nice explanation! I love it.
Good idea!
If you want to know what is happening with recursive backtracking each possible route (assuming the maze is solvable) is made out after each step you take. The program knows all the results before it actually prints back anything to you! Like a teacher grading a paper, you don't know the grade until they tell you. If you step into a wall the code says welp I am done time to free up some memory and undos the step that led you to the wall. Why? Because programming languages keep track of things (like each step in a maze) using a stack of method calls. Once you walk into the brick wall in the maze the program says okay nothing to do here lets pop off all our steps. Oh wait now I can go this way (0-3)
Obviously just imagining you are calling a different, working function is a much simpler way to think about it.😅
it's such an excellent work!
#cons : Type your program while you're explaining otherwise it will be difficult to go through. Explain the concept before hand.
Thanks for your Video👍
Great explanation
Whats the difference between this and DFS?
DFS is an implementation of backtracking for graphs.
Amazing explanation. Really helped, thanks so much.
recursion is so counter-intuitive!
Does the code without recursion actually works?? I've tried to replicate it in ruby but I have found some roadblocks. Probably due to the use of List here... How exactly do the begin() and end() methods work?
The code all works. I've done very little programming in Ruby, so I can't help you there. But I can explain how a list iterator works. Let me start by analogy and see if this helps. Imagine that we declared an array myArray and the constant SIZE specified how many members were in the array. So myArray[0] through myArray[SIZE - 1]. Then begin() would be like setting a variable called arrayPosition to 0, the first index of an array. And end() would give you SIZE, so if arrayPosition == SIZE it means you have advanced arrayPosition off the end of the array. (I think in Ruby you can legally reference elements outside the original range of the array, but you get the idea). Because you can dynamically add elements to arrays in Ruby I think the code should be translatable from C++ lists to Ruby arrays. Let me know if you have any more specific problems and I'll try to help.
Nice video!
Thanks for the useful example of coding with Stacks.
You are welcome. Thanks for checking it out.
great video!
Didn't understand how the recursive part worked
video very easy understand.thanks!
Glad you liked it!
Really nice explanation! :D
thnank you so much the vedio was intersting i would like to use this algorithm to maximize a funtion how can i? thank you in advance
What is this typeface? It's very pleasing
Looks like Consolas to me :)
Sorry for the delay. It's Futura-Book.
very cool
Fantastic!
quality content
Helpful!
Can you please do these in java too?
Best explanation 😎
Thank you! I'm glad you liked it.
can u give me the link of the code that u showed in video?
Amazing pls more
I have a question... how do you use backtracking in finding all possible permutations of arranging n items?
That's the kind of problem where "backtracking" would be implicit and hard to see as such. Let's say you wanted to produce all the permutations of the letters A through Z. Let's suppose the language you are working in has a string library with functions or methods that 1) add a character to the end of a string 2) determine the length of a string 3) gets you the character at a certain position and 4) tells you if a character is in a string.
Then we could write a recursive function to output all permutations of A through Z as follows. Our function has one parameter called PartialPermute. The code in the function would do this:
-- if PartialPermute has 26 characters, output it and end the function (i.e., return)
-- otherwise, loop a variable called Letter from 'A' to 'Z'
---- inside the loop, check to see if Letter is not already in the string PartialPermute
------- if not, copy PartialPermute to TempString, append Letter to TempString, and recursively call this function, passing TempString as the argument
That's pretty much it. Again, backtracking here is implicit. You could make the backtracking more visible by appending Letter directly to PartialPermutre instead of using TempString, and then you would have to strip the last latter off PartialPermute after the recursive call, a kind of backtracking.
Of course, if you wanted to store the results instead of display them or make a more general permutation function this would have to be expanded a bit but that's the basic idea.
Thank you! I have researched a little bit on the subject and your video was the best explanation of even an indirect example of the problem I had. Well done!
I have a doubt,this library that includes "push_back", "empty", "insert", how can i implement in C?
(don't get angry please, i'm still learning, but in C, not C++)
you need to do by your self. They are not included in standard c libraries.
Nicolas Wolyniec thanks
this is great but i wish you could explain the same thing on python :(
would be nice if you used a dark or black background too
The maze problem is basically solved by depth-first search.
Dear TH-cam Algorithm, please give me more of these practical SWE videos and less tech influencer garbage
Oh, if only we could talk directly to the algorithm...anyway, glad you found it helpful.
Nice, but it video is lacking graphical input on what is happening in each step of the backtracking
widce
This explanation is awesome!
*Applause*
define
Dude, In the 1st solution you have used the (!) operator with foundOutlet(line 26) which is declared false. Your program will never enter the second loop.
Remove (!) then the program will work just fine.
In the first program when I'm printing iter at line 25 and line 27(say) i.e before and after the second while loop its giving me {1,0,1,0,1,0,3,4,3,4} and {1,0,2,1,0,2,1,3,0,4,3,5,4,3,5,7,4,8} respectively. Im unable to understand how the iterator is moving.
um no that is wrong, the loop will execute as foundOutlet is set to false, and the second while loop only executes if this boolean value is set to false. if foundOut was set to true then the loop would not execute
where can we get the source code?
U sound like khan academy!
Could you program when you teach instead of talking about the code which has been done?
everyone saying amzing amazing just answer one question why (!foundOutlet) is written in while loop ?
I can try to answer that. Do you mean literally why it's part of the while loop condition? That loop exists to set foundOutlet to true if we find a connection from the current point to an unvisited point. We're not counting how many unvisited points we can reach, we only need to know if we can reach one, or not. So once we find an unvisited point (setting foundOutlet to true), we don't need to continue the loop further. That's why the !foundOutlet condition. Of course there would other ways of accomplishing the same thing. Let me know if this isn't what you meant.
An even better approach is just to make all the right decisions the first time around. Then you never have to backtrack.
Ha! For that you'll need a non-deterministic computer. You still don't make only right decisions, but because you make all possible decisions simultaneously, you can pick the one that ends up at the exit.
Amazing 💗