backtracking-in-datastructure

What is backtracking in data structure?

Hello friends, In this, in this blog post I am going to let you know about one more interesting technique name as backtracking to solve the problem in the data structure. Which most of you would have read during your study period or engineering.

Backtracking is very helpful in solving the problems where we have a set of n number of solutions or in other words, ave multiple solutions for solving one particular problem and then we need to find out the optimal solution for solving that problem by satisfying some constraints too which are the part of this problem.

So ultimately under a fixed boundary or predefine constraints we need to find out the best or optimal solution for the particular problem out of all possible solution of that problem.

In many application of the backtracking method, the desired solution is expressible as an n-tuple(x1, x2, ………Xn), where Xi is chosen from some finite set of Si.

Generally, the problem to be solved calls for finding one vector tha maximizes or satisfies or minimizes a certain function P(x1, x2,…..xn). Sometimes it seeks all vectors that satisfy P.

Many of the problems we solve using backtracking require that all the solutions satisfy a complex set of constraints. these constraints are divided into two categories for any problem. They are listed below.

Explicit Constraints:

Explicit constraints are rules that restrict each Xi to take on values only from a given set

Some examples that are common for explicit constraints are

Xi>=0 or Si ={all non negative real numbers}
Xi=0 or 1 or Si ={0, 1}
Li<=Xi<=Ui or Si={a:Li<=a<=Ui}

The explicit constraints depend on the particular instance I of a problem being solved. All tuples that satisfy the explicit constraints define a possible solution space for I

Implicit Constraints:

Implicit constraints are rules that determine which of the tuple in the solution space of I satisfy the criterion function. Hence implicit constraints give the way in which the Xi must relate to each other.

An example that can be solved by the use of backtracking technique are listed below:

  • Sorting the array of integers in a {1:n}
  • 8 -Queens problem
  • 4- Queens problem
  • Sum of subsets problem.

In the case of any queries, you can write to us at a5theorys@gmail.com we will get back to you ASAP.

Hope! you would have enjoyed this post about backtracking technique.

Please feel free to give your important feedbacks in the comment section below.

Have a great time! Sayonara!