Subset Sum Overlapping subproblems (Dynamic programming)

Question

The link to the question is as follows:
https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
I do not see the overlapping subproblem property being fulfilled in the question atleast for ever input case. For instance in the follwing link, the recursive tree does not have any overlapping subproblem
http://www.zrzahid.com/subset-sum-problem-dynamic-programming/

Also, for instance in the following program there are no overlapping subproblems. I do not understand how dynamic programming helps here, when there are no overlapping subproblems. Please explain.

bool isSubsetSum(int set[],int n, int sum)
{
    if(sum==0)
return true;
if(n==0 || sum<0)
    return false;
return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum);
}
int main()
{
  int set[] = {3, 34, 4, 12, 5, 2};
  int sum = 9;
  int n = sizeof(set)/sizeof(set[0]);
  if (isSubsetSum(set, n, sum) == true)
     printf("Found a subset with given sum");
  else
     printf("No subset with given sum");
  return 0;
}

StPiere StPiere · Accepted Answer · 2017-12-31T12:00:59

Think about it this way:

If there is a sum within set[] elements equals to sum there are 2 distinct possibilities:

the last element (its index is n-1) is included in the sum -> in that case the other n-1 elements sum up to sum - set[n-1]
the last element (its index is n-1) is not included in the sum -> in that case the other n-1 elements sum up to sum.

The OR in the statement: return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum); checks for both possibilities 1. and 2. recursively.

If there are some elements in the set[] equals to sum the recursion at some point will reach the case sum = 0; and it will return true at the downest recursion level, which will propagate the TRUE up to the original call (remember: A OR B returns TRUE if at least one of the A or B is TRUE).

Otherwise you are reaching the case sum not equal to 0 and n equals to 0 which will propagate FALSE.

Subset Sum Overlapping subproblems (Dynamic programming)

1 Answers