Subset with sum closest to zero | Python3 Code for above implementation ; Variable to store states of dp ; Function to return the number closer to integer s ; To find the sum closest to zero Since sum can be negative , we will add MAX to it to make it positive ; Base cases ; Checks if a state is already solved ; Recurrence relation ; Returning the value ; Function to calculate the closest sum value ; Calculate the Closest value for every subarray arr [ i - 1 : n ] ; Driver function ; Input array
import numpy as np NEW_LINE arrSize = 51 NEW_LINE maxSum = 201 NEW_LINE MAX = 100 NEW_LINE inf = 999999 NEW_LINE dp = np . zeros ( ( arrSize , maxSum ) ) ; NEW_LINE visit = np . zeros ( ( arrSize , maxSum ) ) ; NEW_LINE def RetClose ( a , b , s ) : NEW_LINE INDENT if ( abs ( a - s ) < abs ( b - s ) ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT else : NEW_LINE INDENT return b ; NEW_LINE DEDENT DEDENT def MinDiff ( i , sum , arr , n ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( visit [ i ] [ sum + MAX ] ) : NEW_LINE INDENT return dp [ i ] [ sum + MAX ] ; NEW_LINE DEDENT visit [ i ] [ sum + MAX ] = 1 ; NEW_LINE dp [ i ] [ sum + MAX ] = RetClose ( arr [ i ] + MinDiff ( i + 1 , sum + arr [ i ] , arr , n ) , MinDiff ( i + 1 , sum , arr , n ) , - 1 * sum ) ; NEW_LINE return dp [ i ] [ sum + MAX ] ; NEW_LINE DEDENT def FindClose ( arr , n ) : NEW_LINE INDENT ans = inf ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans = RetClose ( arr [ i - 1 ] + MinDiff ( i , arr [ i - 1 ] , arr , n ) , ans , 0 ) ; NEW_LINE DEDENT print ( ans ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 25 , - 9 , - 10 , - 4 , - 7 , - 33 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE FindClose ( arr , n ) ; NEW_LINE DEDENT