Backtracking
What is the backtracking and how do we use it for solving computational problems?
Backtracking solves computational problems that require reversing previously taken steps when an invalid condition or state within a sub-problem is identified. Backtracking problems are usually recursive as the subproblem within a problem is of the same nature. The recursive function defined to solve the problem reverses a previously taken step if an invalid condition of the sub-problem is identified.
Consider the 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.
