I am not able to figure out where is the DP first property of Overlapping subproblem fits in Subset Sum Problem. However, I understand the Optimal Substructure part.While doing the recursive solution of Including and excluding the element where are the problems getting overlapped?
Is it like since it is an NP problem so not having two properties of DP.
The Link to problem is http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
Can someone please help me in understanding this.
5
votes
I would recommend you not to care about these two properties at all. They are not necessary neither to understand and code a dynamic programming solution nor to prove it.
- kraskevich
@ILoveCoding So u mean the above without these two properties also we can find a DP solution? nad do u see any Overlapping Problem in the recursive solution of Subset Sum?
- Art
Nope, I'm trying to say there is no need to use a notion of these two properties(in my opinion, they do not help to solve problems). You can prove the correctness of this solution and analyse its time complexity without them.
- kraskevich
Ok...then how will i come to know that DP can be applied in this particular problem if I dont see the above two properties?
- Art
It is possible to prove the correctness of this solution using mathematical induction.
- kraskevich
1 Answers
4
votes
Let's call the entire set of numbers S = {s[1], ...., s[n]}, the target value k, and write f(X, t) = 1 if there is a subset of X that sums to t, and 0 otherwise. So the answer we want to calculate is f(S, k).
You will get overlapping subproblems whenever two different subsets of numbers have the same sum, and that sum is less than the target k. In detail, suppose there is a subset SI = {s[i_1], ..., s[i_p]} and a different subset SJ = {s[j_1], ..., s[j_q]}, such that sum(SI) = sum(SJ) < k. Suppose w.l.o.g. that the indices are all in order (i.e. a < b implies i_a < i_b and j_a < j_b), and i_1 <= j_1 (if it doesn't, just swap SI and SJ). Then the subproblem f({s[1], ..., s[m-1]}, k-sum(SI)) will arise for (at least) two different paths through the call tree: after starting at f(S, k) (i.e. the root) and choosing to include all numbers in SI and no other numbers with indices >= i_1; and after starting at f(S, k) and choosing to include all numbers in SJ and no other numbers with indices >= j_1, and then choosing to also exclude the next j_1 - i_1 numbers.
Worked Example
Suppose S = {3, 4, 5, 6, 11} and k = 14. Then by excluding the 11 and including the 5 and the 6, we arrive at the subproblem f({3, 4}, 3) (which will have the solution 1) -- this corresponds to choosing SI = {5, 6} and i_1 = 3. Alternatively, by including the 11 and then excluding the 5 and the 6, we again arrive at the subproblem f({3, 4}, 3) -- this corresponds to choosing SJ = {11} and j_1 = 5.
