Grokking Dynamic Programming Patterns for Coding Interviews
Vote

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

On This Page

Problem Statement

Try it yourself