Prerequisite for BackTracking
Backtracking is very useful Concept in Competitive Programming. Beginner’s Found Backtracking difficult to understand. Beginner’s don’t feel confident on Recursion and that is the reason why this concept is difficult for them. Hence for learning Bactracking, it is must that you know what the recursion is.
What is Backtracking
As word Back Tracking is made up of two word’s – Back and Tracking, Hence Tracking from Back. Don’t need to confuse Here! We introduce everything in very easy manner.
First, It is an algorithm Technique which uses recursion to solve problem.
Simple Example of BackTracking
Suppose, You are standing in roundabout and only one direction of roundabout is way to Hospital. Here, You only know is that There are 4 direction of roundabout and one of them leads to your destination and it is also confirms that one of direction must lead to your destination.
So You start going from each direction of roundabout and if you did not find Your destination and you come back to roundabout.
Now you go to second direction, Here What you do is come back and track to next direction, Hence Here you use this concept.
Algorithm Technique – Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.
It is an important tool for solving constraint satisfaction problem such as crosswords, verbal arithmetic, Sudoku and many other puzzles.
It is often the most convenient (if not the most efficient) technique for parsing for the knapsack problem and other combinational problems.
This is also the basis of the so-called logic programming. American mathematician D.H Lehmer was first person who introduce term “backtrack ” in the 1950s
Learn BackTracking by Practise
Easy One –
Example 1 – N Queen Problem
Example 2(Problem Link) – Binary Watch (LeetCode)
Example 3(Problem Link) – Letter Case Permutation (LeetCode)
Example 4 – Rat in a Maze Problem