Subset with sum closest to zero | Java Program for above approach ; 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 Code ; Input array
import java . io . * ; class GFG { static int arrSize = 51 ; static int maxSum = 201 ; static int MAX = 100 ; static int inf = 999999 ; static int dp [ ] [ ] = new int [ arrSize ] [ maxSum ] ; static int visit [ ] [ ] = new int [ arrSize ] [ maxSum ] ; static int RetClose ( int a , int b , int s ) { if ( Math . abs ( a - s ) < Math . abs ( b - s ) ) return a ; else return b ; } static int MinDiff ( int i , int sum , int arr [ ] , int n ) { if ( i == n ) return 0 ; if ( visit [ i ] [ sum + MAX ] > 0 ) return dp [ i ] [ sum + MAX ] ; visit [ i ] [ sum + MAX ] = 1 ; dp [ i ] [ sum + MAX ] = RetClose ( arr [ i ] + MinDiff ( i + 1 , sum + arr [ i ] , arr , n ) , MinDiff ( i + 1 , sum , arr , n ) , - 1 * sum ) ; return dp [ i ] [ sum + MAX ] ; } static void FindClose ( int arr [ ] , int n ) { int ans = inf ; for ( int i = 1 ; i <= n ; i ++ ) ans = RetClose ( arr [ i - 1 ] + MinDiff ( i , arr [ i - 1 ] , arr , n ) , ans , 0 ) ; System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 25 , - 9 , - 10 , - 4 , - 7 , - 33 } ; int n = arr . length ; FindClose ( arr , n ) ; } }