Determine if there is a subset of S that sums to floor(N/2) floor. Given S = {3,1,1,2,2,1}, a valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}.
Let: p(i, j) be True if a subset of {x1, ..., xj} sums to i and False otherwise.
p(i, j) is True if { p(i, j − 1) is True -------(i) p(i − xj, j − 1) is True --------(ii) }
my understanding for (i) equation is: subset of { x1, ..., xj } that doesn't sum up to i but previous j-1 elements may sum up to i my understanding for (i) equation is: subset of { x1, ..., xj } that does use xj and that sums to i − xj (since xj + that subset's sum = i).
However my understanding doesn't work for the (ii) equation (j-1) part.
Why can't we have p(i − xj, j) only?
For case (ii) we are finding a subset of {x1,..,xj} that uses xj and sums to i.
However, we are making this sum by combining xj with a subset of {x1,..,x(j-1)}.
If we had p(i-xj,j) then we would be saying that we can make a total of i by using xj plus a subset of {x1,..xj} and we would be allowed to use xj twice.
For example, if we had the set {1,5,16} then the total is 16+5+1=22 so the target is 11. If you changed the recurrence to have p(i-xj,j) then the algorithm would say that it is possible to get a sum of 11 by using {1,5,5} - Note that we have used 5 twice which should not be allowed.