Sum of subsets nearest to K possible from two given arrays | Stores the sum closest to K ; Stores the minimum absolute difference ; Function to choose the elements from the array B [ ] ; If absolute difference is less then minimum value ; Update the minimum value ; Update the value of ans ; If absolute difference between curr and K is equal to minimum ; Update the value of ans ; If i is greater than M - 1 ; Includes the element B [ i ] once ; Includes the element B [ i ] twice ; Excludes the element B [ i ] ; Function to find a subset sum whose sum is closest to K ; Traverse the array A [ ] ; Function Call ; Return the ans ; Driver Code ; Input ; Function Call
ans = 10 ** 8 NEW_LINE mini = 10 ** 8 NEW_LINE def findClosestTarget ( i , curr , B , M , K ) : NEW_LINE INDENT global ans , mini NEW_LINE if ( abs ( curr - K ) < mini ) : NEW_LINE INDENT mini = abs ( curr - K ) NEW_LINE ans = curr NEW_LINE DEDENT if ( abs ( curr - K ) == mini ) : NEW_LINE INDENT ans = min ( ans , curr ) NEW_LINE DEDENT if ( i >= M ) : NEW_LINE INDENT return NEW_LINE DEDENT findClosestTarget ( i + 1 , curr + B [ i ] , B , M , K ) NEW_LINE findClosestTarget ( i + 1 , curr + 2 * B [ i ] , B , M , K ) NEW_LINE findClosestTarget ( i + 1 , curr , B , M , K ) NEW_LINE DEDENT def findClosest ( A , B , N , M , K ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT findClosestTarget ( 0 , A [ i ] , B , M , K ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 2 , 3 ] NEW_LINE B = [ 4 , 5 , 30 ] NEW_LINE N = len ( A ) NEW_LINE M = len ( B ) NEW_LINE K = 18 NEW_LINE print ( findClosest ( A , B , N , M , K ) ) NEW_LINE DEDENT