backtracking

BackTracking In C | Complete Overview Of BackTracking

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.

BackTracking - geekstocode

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.

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 in C 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

Sudhanshu is Technology geek and also a pro pubg player. I like to create content in my free time that helps others. Currently pursuing BCA from Noida and operating Geekstocode

Leave a Comment

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