educative.io

In the dp solution, handling only one number soluton

Courses
,
#1

hey, I got a bit confused. in below codes. if only one number, based on what I understood, it will not have two subsets which will be equal. for example, {1}, it could have subset {1},{}. based on the codes, dp[0][1] will be true. However it should be false as there is not other subset which is also {1}. could you help to explain? Thanks.
From line 23,
// with only one number, we can form a subset only when the required sum is equal to its value
for(int s=1; s <= sum ; s++) {
dp[0][s] = (num[0] == s ? true : false);
}

#3

Hi @Peng_Xu,

You are right with one element we can’t have two subsets with equal sum. That is why we have transformed our problem to find one subset (NOT two subsets) with a sum equal to S/2. See the following line for reference:

// we are trying to find a subset of given numbers that has a total sum of ‘sum/2’.
sum /= 2;

So now we are only finding one subset with a sum equal to half of the required sum.

Hope this clarifies your question.

2 Likes
#4

Thanks for the quick response. Technically, finding one subset with a sum equal to half of the required sum, the logic is correct. But in the real data, i.e. {1} , there will be no data(except 0) which is equals to half of itself. So basically, the dp[0][s] will always be false for this question.
for(int s=1; s <= sum ; s++) {
dp[0][s] = false;
}

So, my guess the logic to " finding one subset with a sum equal to half of the required sum" is just using it as a template(pattern) of Pattern 0/1 Knapsack. Please correct me if I was wrong. Thank you.