Backtracking Algorithms
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time. The backtracking algorithm is derived from the recursion algorithm, with the option to revert if a recursive solution fails; i.e., in case a solution fails, the program traces back to the moment where it failed and builds on another solution. So basically it tries out all the possible solutions and finds the correct one.
Dynamic Programming
Dynamic programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using dynamic programming.
| It is to use the previously calculated result to avoid repeated calculations of the same subtask which helps in reducing the time complexity. |
|
|
Pattern Searching
They are sometimes also referred to as string searching algorithms and are considered as a part of the string algorithms. These algorithms are useful in the case of searching a string within another string. |
|