Prerequisite for Backtracking
The backtracking (in c) concept is very useful in Competitive Programming. Beginner’s Found Backtracking difficult to understand. Beginner’s don’t feel confident about Recursion and that is the reason why this concept is difficult for them. Hence for learning Backtracking, it is a must that you know what the recursion is.
What is Backtracking
As word Back Tracking is made up of two words – Back and Tracking, Hence Tracking from Back. Don’t need to confuse Here! We introduce everything in a very easy manner.
First, It is an algorithm Technique which uses recursion to solve the problem.
Simple Example of BackTracking
Suppose, You are standing in a roundabout and only one direction of the roundabout is way to Hospital. Here, You only know is that There is 4 directions of the roundabout and one of them leads to your destination and it is also confirmed that one of direction must lead to your destination.
So You start going from each direction of the roundabout and if you did not find Your destination and you come back to the roundabout.
Now you go to the second direction, Here What you do is come back and track to the 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
Practice Backtracking in C by following examples
Easy One –
Example 1 – N Queen Problem
Problem 2(Problem Link) – Binary Watch (LeetCode)
Example 3(Problem Link) – Letter Case Permutation (LeetCode)
Example 4 – Rat in a Maze Problem