DSA: Understand The Concept Of Backtracking
Backtracking is a form of recursion.
Backtracking is an improvement of the brute force approach. It systematically search for a solution to a problem among all available options. Backtracking can be thought of as a selective tree/graph traversal method. The tree is a way of representing some initial starting position (the root node) and a final goal state (one of the leaves.)
What is Backtracking: It is use when you have multiple solutions to a given problem and you want all those solution.
This is one of problem solving strategy. By using this we can solve to the problem or write an algorithm. This strategy use brute force approach. Let’s understand the brute force approach.
What is Brute Force: For any given problem, we should try out all the solutions and pick up desired solution. Here we are not talking about the optimize solutions.
Let’s understand the strategy with an example:
We have three cars(BMW, Mercedes, and Audi) and we have to park all the three cars.
So first the question comes in our mind is that how many ways we have? The answer is we have three number so the ways will be factorial of three. 3! means we have six ways to do. let’s find out all possible arrangements and the solution will be showing in a tree format that is solution tree and also called state-space tree. Find the below diagram.
Usually In backtracking, Problems may have some constraints and we will try to check those constraints and get the desire solutions. So we take a constraint in our example that is BMW Car should not parked in middle.
Let’ revised all the case again with the below diagram:
Here we applied the bounding function and kill the node (2 and 6) and we got four solutions.
If no bounding function applied until you reached last level then you got a solution.
One more thing that is the same approach used by one more strategy called an Branch and Bound. Let’s understand the difference in the below diagram:
So the meaning is Backtracking first complete the last node then backtrack whereas Branch and Bound generate breadth wise.
That’s it. I hope it will help to understand easily. More about the data structure stay tuned to my articles and for motivating me please clap.
Thank you for reading.
Have a joyful day.