educative.io

I the Minimum Subset Sum Difference Solution is wrong

Courses
, ,
#1

If we test with the set {1,2,3,9} the result is 3 but if I change the order to {9,1,2,3} the result turns to 7 and it shouldn’ have been affected.

1 Like
#3

Hi @Arturo_Bravo_Reynaga

Can you please provide the link to the course and lesson you are following, so I can help you better with it?

Thank you :blush:

#4

Hi @Abdul_Mateen! @Arturo_Bravo_Reynaga is right, there is an error.

These are the links to the course and lesson:
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5390739594805248

The problem is in the Bottom-up Dynamic Programming solution. With can_partition([9, 1, 2, 3]) I don’t get 7, but 5, which is also wrong. Should be 3.

I think the problem is in the lines 11 and 12, that read:

  for j in range(0, int(s/2)+1):
    dp[0][j] = num[0] == j

They should be:

  for j in range(1, int(s/2)+1):
    dp[0][j] = num[0] == j

Otherwise you overwrite the True value of the cell dp[0][0] with False.