Is this recurrence relation correct for the subset sum problem?
Statement: Print Yes or No depending on whether there is a subset of the given array a[ ] which sums up to a given number n.
dp[i][j] = true, if 0 to j elements in array sum up to i and false otherwise.
dp[i][j] = min(dp[i-a[j]][j], dp[i][j-1])
Base case values :
dp[0][0] = true
dp[1...i][0] = false
Just trying to see if I have the recurrence relation right or not.Thanks for guiding.
You are almost correct ( not sure why you used min ). But let dp[i][j] store the answer of whether a subset of arr[0],arr[1],....arr[j] (here arr[] is the array of elements ) can sum upto i. That is dp[i][j] is 1 if answer is yes and 0 if answer is no. Ignoring the base cases, the recurrence relation is dp[i][j]=(dp[i][j-1] | dp[i-arr[j]][j-1]). To get the exact code and base cases and implementation you can have a look here : http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/.