Backtracking

What is the backtracking and how do we use it for solving computational problems?

Backtracking is an algorithmic technique for solving a class of computational problems that require reversing previously taken steps when an invalid condition or state is identified. Backtracking problems are usually recursive in nature as the subproblem within a problem are of the same nature. The recursive function has a way to reverse a previously taken step that does not lead to the solution to the problem.

Consider a simple example of partitioning an integer 10 using integer parts 6 and 5. If a part 6 is chosen to be included; we are left with 10 - 6 = 4. Partitioning the deficit 4 is similar to the previous problem of partitioning 10 thus indicating recursion. Also the deficit 4 can never be partitioned using parts 5 and 6. Thus the previously included part 6 would lead to an invalid state of partitioning part 4 using available integers 6 and 5. Hence, we reverse our previous step of including part 6 i.e. we backtrack our steps and move to the next available part 5.

Backtracking_Example



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.