I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result.

My questions are.

  1. How did someone conclude that the Last row's last column will give us the result?
  2. How can we trace from there to check the subset that can be added to get the Sum?
  3. Finally, is there a way to trace all the possible subsets from this DP table?

Thanks in advance.

  • 1
    $\begingroup$ Hi Manoj, you need to focus your post to one single question. As of now it feels broad. Go through Subset sum problem so many times so that you understand it lot better. Then read this link to get your answers geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum. $\endgroup$ – Shridhar R Kulkarni Apr 29 at 4:43
  • $\begingroup$ Moreover, I don't know what "Last row" or "last column" means in this setting. You will have to describe the dynamic programming algorithm you are referring to. $\endgroup$ – Yuval Filmus Apr 29 at 7:40
  • $\begingroup$ @Shridhar R Kulkarni Thanks for your comment. I understood and I have written code too using Swift for Both DP and Backtracking approach. Perfect Sum Problem in geek for geeks is not that efficient. It's using both DP and Brute Force to print the result. That's y I actually came here. $\endgroup$ – Manoj Apr 29 at 13:15
  • $\begingroup$ @ Yuval Filmus It's too broad the explain it here, sorry. I thought someone who's already trying to solve the NP-Complete problems can help me. $\endgroup$ – Manoj Apr 29 at 13:17
  • $\begingroup$ @Manoj: DP is used to figure out if subset exists. What you say brute force is not really brute force if you trace. It is just backtracking on the DP table that has been constructed. As all the subsets need to be printed, algorithmic complexity can't be better. $\endgroup$ – Shridhar R Kulkarni Apr 29 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.