Subset Sum Dynamic Programming - Overlapping SubProblems

Question

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.

Answer 1

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.