text: Dynamic Programming | CPP program for the above approach ; Taking the matrix as globally ; Check if possible subset with given sum is possible or not ; If the sum is zero it means we got our expected sum ; If the value is not - 1 it means it already call the function with the same value . it will save our from the repetition . ; if the value of a [ n - 1 ] is greater than the sum . we call for the next value ; Here we do two calls because we don ' t ▁ know ▁ which ▁ value ▁ is ▁ ▁ full - fill ▁ our ▁ criteria ▁ ▁ that ' s why we doing two calls ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int tab [ 2000 ] [ 2000 ] ; int subsetSum ( int a [ ] , int n , int sum ) { if ( sum == 0 ) return 1 ; if ( n <= 0 ) return 0 ; if ( tab [ n - 1 ] [ sum ] != -1 ) return tab [ n - 1 ] [ sum ] ; if ( a [ n - 1 ] > sum ) return tab [ n - 1 ] [ sum ] = subsetSum ( a , n - 1 , sum ) ; else { return tab [ n - 1 ] [ sum ] = subsetSum ( a , n - 1 , sum ) || subsetSum ( a , n - 1 , sum - a [ n - 1 ] ) ; } } int main ( ) { memset ( tab , -1 , sizeof ( tab ) ) ; int n = 5 ; int a [ ] = { 1 , 5 , 3 , 7 , 4 } ; int sum = 12 ; if ( subsetSum ( a , n , sum ) ) { cout << " YES " << endl ; } else cout << " NO " << endl ; }