Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Minimum Subset Sum Difference

Problem Statement

Try it yourself

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'. Following are the two subsets: {1, 2, 5} & {7, 1}.

Example 3:

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

Constraints:

  • 1 <= n <= 15
  • nums.length == 2 * n
  • -10<sup>7</sup> <= nums[i] <= 10<sup>7</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
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

· 3 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.

On This Page

Problem Statement

Try it yourself