To watch the video explaining this topic, please click here.
Backtracking is a technique when using recursion (DFS). The trick is:
Basically, because DFS is deterministic and goes in a "depth-first" order, at each level we can edit information, which keeps the "state" of our system the way we need it to for the next level's recursive calls, and then we can undo the change we made for whenever we go back up to the previous level.
A good analogy of this is a kitchen. Pretend we have a kitchen that only one person is going to use at a time.
Similarly, using backtracking in DFS means we can have shared variable without having to create a new one for each recursive call. This saves time and memory.
[Leetcode Medium] Word Search (Boggle Problem)
Given a 2D board of tiles (letters) and a word, check if the word exists in the board.
We'll try each tile as the beginning of our traversal, and what we'll recursively do is:
The "backtracking" part of this solution is that we're changing shared state (step 2), making recursive calls, and then undoing our change for when we go back up to previous levels.
Here's pseudocode for our solution to the boggle problem:
Full Code (C++)
The full C++ code, which corresponds to the "Word Search" problem on Leetcode, is as follows:
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.