Hello,
I try to submit my solution into Leetcode as an extra check and to look for alternative solutions. This problems is categorised under backtracking, which can indeed be used. However, it will not give the optimal solution. The optimal solution uses Dynamic Programming.
As a suggestion it might be a good idea to split this question up into two parts; One where you explicitly state that you should use backtracking (noting that this solution is not optimal) and the other that you should use dynamic programming. It would be a good exercise!
Please see the freely available leetcode editorial for more details!
Kind regards,
Riaan
Course: https://www.educative.io/collection/10370001/5500262945128448
Lesson: https://www.educative.io/collection/page/10370001/5500262945128448/5228921996181504