Introduction To Backtracking Programming

What is Backtracking Programming??

Recursion is the key to backtracking programming. As the name suggests we backtrack to find the solution. We start with one possible move out of many available moves and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other move and try to solve it. If none of the moves work out we will claim that there is no solution to the problem.

Generalized Algorithm:

Pick a starting point. 
while(Problem is not solved)
	For each path from the starting point.
		check if selected path is safe, if yes select it and make recursive call to rest of the problem
		If recursive calls returns true, then return true.
		else undo the current move and return false. 
	End For
	If none of the move works out, return false, NO SOLUTON.

Click here to read about - Problems on Backtracking

Also Read:

- Find a peak element in a Given Array Beginner
- Determine whether given binary tree is binary search tree(BST) or not Medium
- Dynamic Programming - Count all paths in 2D Matrix with Obstructions in it Medium
- Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern Hard
- Find all subsets of size K from a given number N (1 to N) Medium
- Lowest Common Ancestor in a Binary Search Tree. Medium
- Print All The Nodes Which are X distance from the Given Node Hard
- Find the Max element in a Given Binary Tree Beginner