Backtracking | Algorithm for Backtracking


Backtracking is an algorithmic technique for recursively solving problems by trying to build a solution incrementally, one piece at a time, removing the solutions that fail to meet the constraints of the problem at any time (for example, time, here it is referred to the time elapsed until reaching any level of the search tree).

According to the wikipedia definition,

Backtracking can be defined as a general algorithmic technique that considers the search for all possible combinations in order to solve a computational problem.

There are three types of backtracking problems –

Decision problem              –  In Decision problem we are looking for a feasible solution.(What is feasible solutions among all solutions possible).
Optimization problem      – In Optimization problem we are looking for the best solution(What is best solution among all possible solutions possible).
Problem of enumeration  – In Problem of enumeration we find all the feasible solutions(What is feasible solutions among all solutions possible).

Search space and optimization problem techniques Backtracking

General method

Two versions of backtracking algorithms

Solution needs only to be feasible (satisfy problem’s constraints)  sum of subsets

Solution needs also to be optimal knapsack problem

The backtracking method

  • A given problem has a set of constraints and possibly an objective function
  • The solution optimizes an objective function, and/or is feasible.
  • We can represent the solution space for the problem by using a state space tree
    The root of the tree represents 0 choices,
    Nodes at depth 1 represent the first choice
    Nodes at depth 2 represent the second choice, etc.
    In this tree a path from a root to a leaf represents a candidate solution
  • Problem space consists of states (nodes) and actions (paths that lead to new states).
  • If a node leads to failure go back to its “parent” node.
  • Characteristics of Brute Force and Backtracking
    Brute force algorithms are slow
    They don’t employ a lot of logic
    But, brute force algorithms are fairly easy to implement as a first pass solution Backtracking is a form of a brute force algorithm


Goals of Backtracking Possible goals

  • Find a path to success
  • Find all paths to success
  • Find the best path to success

Not all problems are exactly alike, and finding one success node may not be the end of the search

Pseudo code for recursive backtracking algorithms

  • If at a solution, report success
  • for ( every possible choice from current state / node)
    Make that choice and take one step along path
    Use recursion to solve the problem for the new node / state
    If the recursive call succeeds, report the success to the next high level
    Back out of the current choice to restore the state at the beginning of the loop.
  • Report failure

Algorithm for Backtracking

void checknode(node v)
  node u;
  if promising(v) then
    if (there is a solution at v) then
       write the solution ;
       for (each child u of v) do


Topic : Backtracking | Algorithm for Backtracking

Leave a Reply