Interview Bootcamp

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

· 4 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

· a month 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.