问最小子集差码显示错误输出

EN

import sys

def subset_sum(arr, n, S, dp):
    # If sum is 0, then answer is 1
    if(S==0):
        return 1

    # If sum is not 0 and set is empty,
    # then answer is 0
    if(n==0):
        return 0

    # If the value is not -1 it means it
    # already call the function
    # with the same value.
    # it will save our from the repetition.
    if(dp[n-1][S]!=-1):
        return dp[n-1][S]

    # if the value of a[n-1] is
    # greater than the sum.
    # we call for the next value
    if(S<arr[n-1]):
        dp[n-1][S] = subset_sum(arr, n-1, S, dp)

    else:
        # Here we do two calls because we
        # don't know which value is
        # full-fill our criteria
        # that's why we doing two calls
        dp[n-1][S] = subset_sum(arr, n-1, S, dp) or subset_sum(arr, n-1, S-arr[n-1], dp)
    return dp[n-1][S]

def minimum_subset_diff(arr, n):
    S = 0

    # Calculate sum of all elements
    for i in range(n):
        S += arr[i]
    
    # Create an 2d list to store
    # results of subproblems
    global dp
    dp = [[-1 for _ in range(S+1)] for _ in range(n+1)]

    # Fill the partition table
    # using memoization approach
    subset_sum(arr, n, S, dp)

    # Find the largest i such that dp[n][i]
    # is true where i loops from S (sum) t0 0
    diff = sys.maxsize
    for i in range(S):
       if  dp[n][i] == 1:
           
           # if S has partition of s1 and s2
           # then difference is s2-s1 => (S-s1)-s1 => S-2s1
           # hence, S-2*i is formed
           # and here we take absolute value
           if(abs(S-2*i) < diff):
               diff = abs(S-2*i)

    return diff

# Driver Code  
if __name__ == '__main__':
    arr = [1, 2, 7]
    n = len(arr)
    print(minimum_subset_diff(arr, n))

9223372036854775807

4