educative.io

Educative

0/1 Knapsack (Dynamic Programming) - Subset Sum (medium)

Hi,

I think there’s a mistake in the C++ optimized code - lines 12-15 are currently:
// populate the sum=0 columns, as we can always form ‘0’ sum with an empty set
for (int i = 0; i < n; i++) {
dp[i] = true;
}

And should just be:
// populate the sum=0 column, as we can always form ‘0’ sum with an empty set
dp[0] = true;

The above lines are especially problematic if the sum is greater than the number of elements in num.

The Java code is correct.
Thanks!