CODEWITHSUNDEEP
c++dynamic-programmingsubset-sum
Neha Sharma
Neha Sharma

Reputation: 295

Subset Sum Overlapping subproblems (Dynamic programming)

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;
}

Upvotes: 0

Views: 361

Answers (2)

NNP
NNP

Reputation: 3451

You probably already figured it out. Say for ex, if the input is [1, 2, 3, 4, 5, 9] and the target sum is say 15, then when [4, 5] are selected OR [9] is selected, [1,2,3] is evaluated twice (thus overlapping subproblems) - to get 15. i.e.; [1, 2, 3, 4, 5] and [1, 2, 3, 9]. Based on the target sum there is the probability that there won't be overlapping problems. To solve this problem though - we do solve sub problems to find the answer.

That's why it's pseudo-polynomial as long as the target sum is reasonable (for ex, say the target sum is < [long (2 ^n] = or, N] - its indeed polynomial. Unlike other well-known DP problems like factorial (O(N)) and longest common subsequence between two strings of length m and n are O(M * N).

So, it depends on the input and target sum to see the overlapping problems.

Also found the following linked answer (and thread) interesting as this talks about why it's a weakly NP-complete problem (https://stackoverflow.com/a/4359673/997661)

Upvotes: 0

StPiere
StPiere

Reputation: 4243

Think about it this way:

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

  1. 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]

  2. 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.

Upvotes: 0

Related Questions