text: Dynamic Programming | A recursive solution for subset sum problem ; Returns true if there is a subset of set [ ] with sum equal to given sum ; Base Cases ; If last element is greater than sum , then ignore it ; else , check if sum can be obtained by any of the following : ( a ) including the last element ( b ) excluding the last element ; Driver code
code: #include <iostream> NEW_LINE using namespace std ; bool isSubsetSum ( int set [ ] , int n , int sum ) { if ( sum == 0 ) return true ; if ( n == 0 ) return false ; if ( set [ n - 1 ] > sum ) return isSubsetSum ( set , n - 1 , sum ) ; return isSubsetSum ( set , n - 1 , sum ) || isSubsetSum ( set , n - 1 , sum - set [ n - 1 ] ) ; } int main ( ) { int set [ ] = { 3 , 34 , 4 , 12 , 5 , 2 } ; int sum = 9 ; int n = sizeof ( set ) / sizeof ( set [ 0 ] ) ; if ( isSubsetSum ( set , n , sum ) == true ) cout << " Found ▁ a ▁ subset ▁ with ▁ given ▁ sum " ; else cout << " No ▁ subset ▁ with ▁ given ▁ sum " ; return 0 ; }