Subset with sum closest to zero | Variable to store states of dp ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define arrSize  51 NEW_LINE #define maxSum  201 NEW_LINE #define MAX  100 NEW_LINE #define inf  999999 NEW_LINE int dp [ arrSize ] [ maxSum ] ; bool visit [ arrSize ] [ maxSum ] ; int RetClose ( int a , int b , int s ) { if ( abs ( a - s ) < abs ( b - s ) ) return a ; else return b ; } int MinDiff ( int i , int sum , int arr [ ] , int n ) { if ( i == n ) return 0 ; if ( visit [ i ] [ sum + MAX ] ) 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 ] ; } 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 ) ; cout << ans << endl ; } int main ( ) { int arr [ ] = { 25 , -9 , -10 , -4 , -7 , -33 } ; int n = sizeof ( arr ) / sizeof ( int ) ; FindClose ( arr , n ) ; return 0 ; }