educative.io

Educative

Count of substrings using recursion and top down approach

How can we implement the same function using pure recursion and memoization?
We cannot simply add the nodes in the recursion tree which return 1. In doing so we would be adding some nodes multiple times due to the substructure present in the problem.

Hi @Kushal, you’re right. We cannot simply add overlapping sub-problems in the recursion tree, which is why we need memoization.

Your query also seems to be already answered on another thread, where you’ll find your recursive example. You can reply to this thread if you have any further questions.