O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Greedy algorithms and backtracking

What do we mean by greedy algorithms? What is backtracking? By being greedy, the algorithm matches the longest possible part. Backtracking algorithms, upon failure, keep exploring other possibilities. Such algorithms begin afresh from where they had originally started, hence they backtrack (go back to the starting point).

We all follow the process of backtracking in real life. For example, to get to an address, we go to a well-known landmark, then try the first lane, for example. If there is no success, we backtrack to the landmark again and try another lane (we may ask a passerby for help). We keep doing this until we get to the address or give up the search altogether.

A well-known example of greedy and backtracking ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required