Sum of subsets nearest to K possible from two given arrays | C ++ program of the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ans = INT_MAX ; int mini = INT_MAX ; void findClosestTarget ( int i , int curr , int B [ ] , int M , int K ) { if ( abs ( curr - K ) < mini ) { mini = abs ( curr - K ) ; ans = curr ; } if ( abs ( curr - K ) == mini ) { ans = min ( ans , curr ) ; } if ( i >= M ) return ; findClosestTarget ( i + 1 , curr + B [ i ] , B , M , K ) ; findClosestTarget ( i + 1 , curr + 2 * B [ i ] , B , M , K ) ; findClosestTarget ( i + 1 , curr , B , M , K ) ; } int findClosest ( int A [ ] , int B [ ] , int N , int M , int K ) { for ( int i = 0 ; i < N ; i ++ ) { findClosestTarget ( 0 , A [ i ] , B , M , K ) ; } return ans ; } int main ( ) { int A [ ] = { 2 , 3 } ; int B [ ] = { 4 , 5 , 30 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int M = sizeof ( B ) / sizeof ( B [ 0 ] ) ; int K = 18 ; cout << findClosest ( A , B , N , M , K ) ; return 0 ; }