Minimum Subset Sum Difference

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

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?

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

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]

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.

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 :(