BackTracking| Complete Overview of BackTracking

backtracking

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.

BackTracking - geekstocode

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.

Professional Definition

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

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *