text: Dynamic Programming | A Dynamic Programming solution for subset sum problem ; Returns true if there is a subset of set [ ] with sun equal to given sum ; The value of subset [ i ] [ j ] will be true if there is a subset of set [ 0. . j - 1 ] with sum equal to i ; If sum is 0 , then answer is true ; If sum is not 0 and set is empty , then answer is false ; Fill the subset table in botton up manner ; print table ; Driver code
code: #include <stdio.h> NEW_LINE bool isSubsetSum ( int set [ ] , int n , int sum ) { bool subset [ n + 1 ] [ sum + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) subset [ i ] [ 0 ] = true ; for ( int i = 1 ; i <= sum ; i ++ ) subset [ 0 ] [ i ] = false ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= sum ; j ++ ) { if ( j < set [ i - 1 ] ) subset [ i ] [ j ] = subset [ i - 1 ] [ j ] ; if ( j >= set [ i - 1 ] ) subset [ i ] [ j ] = subset [ i - 1 ] [ j ] || subset [ i - 1 ] [ j - set [ i - 1 ] ] ; } } for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= sum ; j ++ ) printf ( " % 4d " , subset [ i ] [ j ] ) ; printf ( " STRNEWLINE " ) ; } return subset [ n ] [ sum ] ; } 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 ) printf ( " Found ▁ a ▁ subset ▁ with ▁ given ▁ sum " ) ; else printf ( " No ▁ subset ▁ with ▁ given ▁ sum " ) ; return 0 ; }