Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Minimum Subset Sum Difference

Problem Statement

Given a set of positive numbers, partition the set into two subsets with minimum difference between their subset sums.

Example 1:

Input: {1, 2, 3, 9}
Output: 3
Explanation: We can partition the given set into two subsets where minimum absolute difference 
between the sum of numbers is '3'. Following are the two subsets: {1, 2, 3} & {9}.

Example 2:

Input: {1, 2, 7, 1, 5}
Output: 0
Explanation: We can partition the given set into two subsets where minimum absolute difference 
between the sum of number is '0'

.....

.....

.....

Like the course? Get enrolled and start learning!
Zac Bolton

Zac Bolton

· a year ago

The initialization for the first row in the bottom up DP approach is:

    # with only one number, we can form a subset only when the required sum is equal to 

    # that number

    for j in range(0, int(s/2)+1):

      dp[0][j] = num[0] == j

However this is wrong and could cause compounding wrong answers resulting in an incorrect output.

The issue is that it overwrites the dp[0][0] cell to False, when it should be true. The fix is to start the for loop at 1, instead of 0.

    for j in range(1, int(s/2)+1):

      dp[0][j] = num[0] == j
Show 1 reply
J

J

· 4 years ago

Bottom-up DP solution fails test case [53,54,3,61,67] for LC 1049. Last Stone Weight II https://leetcode.com/problems/last-stone-weight-ii/description/

N

Naresh Ch

· 4 years ago

would some version of knapsack solution still apply if the set contained negative numbers?

Would be really helpful if negative numbers solution was also discussed here.

Thanks!

Show 1 reply

Reading Progress

0%

Vote for new content