Book question. Explain this solution of Subset Sum problem.
Code: https://paste.mod.gg/hqxraqfhdgeg/0
Copy/pasted from last solution here: https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
But I don't understand it.
I want to understand what, why and how.
My solution was to generate all combinations without repetition but its obviously very slow.
BlazeBin - hqxraqfhdgeg
A tool for sharing your source code with the world!
GeeksforGeeks
Dynamic Programming - Subset Sum Problem - GeeksforGeeks
Recursive and Dynamic Programming solutions for subset sum problem, Pseudo polynomial algorithm. C code for subset sum problem.
1 Reply
I ended up using the third approach mentioned here: https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
YouTube videos which I found helpful:
1. https://youtu.be/s6FhG--P7z0?si=HEvbMCp16XorcidT
2. https://youtu.be/34l1kTIQCIA?si=B8WddoCJSf5KBVu1
GeeksforGeeks
Dynamic Programming - Subset Sum Problem - GeeksforGeeks
Recursive and Dynamic Programming solutions for subset sum problem, Pseudo polynomial algorithm. C code for subset sum problem.
Tushar Roy - Coding Made Simple
YouTube
Subset Sum Problem Dynamic Programming
Given a set of non negative numbers and a total, find if there exists a subset in this set whose sum is same as total.
https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubsetSum.java
https://github.com/mission-peace/interview/wiki
Techdose
YouTube
subset sum problem dynamic programming | backtracking sum of subsets
This is a video lecture which explains subset sum problem solving using both backtracking and dynamic programming methods. This explanation is a little long but once you watch it, you won't ever regret about having watched such a long video. Backtracking takes exponential time to solve the subset sum problem therefore, we solve using it dynamic ...