educative.io

Solution clarifications

Courses
,
#1

The solution for this task seems to have logic that differentiates from a backtracking approach.
It looks like just a recursion with dfs. Backtracking should explore all possible combinations and backtracking whenever we encounter an invalid combination. But there is no condition when we encounter an invalid combination and do backtracking. Could you please explain why this solution is a backtracking one?
Thanks,

Regards, Anna

Course: https://www.educative.io/collection/10370001/6593625897304064
Lesson: https://www.educative.io/collection/page/10370001/6593625897304064/6290705830117376

#2

Hello @Anna,

Thank you for sharing your feedback. The solution code does follow the backtracking pattern, let’s see how does it explore all possible paths and applies backtracking.

It is a two step solution, in the first step it is simple dfs + recursion. However the actual backtracking is being carried out at second step. In the second step the solution backtracks by returning the maximum value from the pair [include_root, exclude_root] at each node. This allows the recursive calls to propagate the maximum value upwards in the tree until the root node is reached. The decision making is being performed at line number 7 where the maximum value is chosen among the both values.

Hope this answers your query. Feel free to share more queries and feedbacks.

Thanks and regards,
Dian

1 Like