Dynamic Programming | Returns true if there is a subset of set [ ] with sum 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 bottom up manner ; uncomment this code to print table ; Driver code
def isSubsetSum ( set , n , sum ) : NEW_LINE INDENT subset = ( [ [ False for i in range ( sum + 1 ) ] for i in range ( n + 1 ) ] ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT subset [ i ] [ 0 ] = True NEW_LINE DEDENT for i in range ( 1 , sum + 1 ) : NEW_LINE INDENT subset [ 0 ] [ i ] = False NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , sum + 1 ) : NEW_LINE INDENT if j < set [ i - 1 ] : NEW_LINE INDENT subset [ i ] [ j ] = subset [ i - 1 ] [ j ] NEW_LINE DEDENT if j >= set [ i - 1 ] : NEW_LINE INDENT subset [ i ] [ j ] = ( subset [ i - 1 ] [ j ] or subset [ i - 1 ] [ j - set [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( n + 1 ) : NEW_LINE for j in range ( sum + 1 ) : NEW_LINE print ( subset [ i ] [ j ] , end = " ▁ " ) NEW_LINE print ( ) NEW_LINE return subset [ n ] [ sum ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT set = [ 3 , 34 , 4 , 12 , 5 , 2 ] NEW_LINE sum = 9 NEW_LINE n = len ( set ) NEW_LINE if ( isSubsetSum ( set , n , sum ) == True ) : NEW_LINE INDENT print ( " Found ▁ a ▁ subset ▁ with ▁ given ▁ sum " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ subset ▁ with ▁ given ▁ sum " ) NEW_LINE DEDENT DEDENT