Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Minimum Subset Sum Difference

Problem Statement

Given a set of positive numbers, partition the set into two subsets with a 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 the 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 the minimum absolute difference 
between the sum of numbers is '0'

.....

.....

.....

Like the course? Get enrolled and start learning!
Sarthuak Sharma

Sarthuak Sharma

· 2 years ago

The constraints should be updated as this solution will not work for all negative numbers

G

Gary

· 4 years ago

Is there a typo in last diagram for Bottom-up Dynamic Programming section where it says, "sum: 1-7, index:1=> (dp[index-1][sum] , as the 'sum' is always less than the number (9)"

shouldn't the index be 3 instead of 1?

M

Michael Shum

· 4 years ago

The Space Complexity of Brute Force should be O(2^n) like the Time complexity? given the Space is driven by the # of calls aka the call stack, same as Time complexity

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:

  def canPartition(self, num):
    def solve(index, left, right, memo):
      
      # return from the cache if found
      if index in memo and str(left) + str(right) in memo[index]:
        return memo[index][str(left) + str(right)]

      # base case
      if index == len(num):
        return abs(left - right)
      
      # recursive with / without item at index
      result = min(solve(index + 1, left, right, memo), solve(index + 1, left - num[index], right + num[index], memo))

      # cache the result
      if index not in memo:
        memo[index] = {}
      memo[index][str(left) + str(right)] = result

      return result
  
    return solve(0, sum(num), 0, {})
Online Courses

Online Courses

· 5 months ago

My solution: T = O(NxT), were N is the number of elements and T is the total of all the elements

S = O(T)

def canPartition(self, num):
    n = len(num)

    if n == 0:
      return -1
    
    total = sum(num)

    # state
    dp = [float('inf')] * (total + 1)

    # base case
    for s1 in range(total + 1):
      dp[s1] = abs(2 * s1 - total)
    
    # recurrence
    for idx in range(n - 1, -1, -1):
      for s1 in range(total + 1):
        dp[s1] = min(
          dp[s1 + num[idx]] if s1 + num[idx] <= total else float('inf'),
          dp[s1],
        )
    
    return dp[0]
Y

yong.9900

· 2 months ago

don't think this is a valid question if (-10^7, 10^7). You will need a big dp array since the sum can be very volatile.

Rohit Bhanot

Rohit Bhanot

· 17 days ago

This course feels more like give a problem and then just solutions. There is no reasoning being built here, author simply says this is a variation of 0/1 Knapsack and can be turned into Subset Sum problem, without even explaining Why and How !! There are tons of free youtube videos that goes into lot more details of why and what !

There is no reasoning or pattern building happening here from 1 problem to another. Whats the point if dont even explain

How this problem relates to 0/1 Knapsack and how to approach it rather than just dumping the solution. There is no explanation of what is even a overlapping sub-problem in this case !

If intent was to give a solution that folks can memorize, then job well done !!

This is not upto the mark :(