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!
A

Anonymous

· 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, {})
A

Anonymous

· 2 years ago

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

A

Anonymous

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

Anonymous

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

Reading Progress

0%

Vote for new content