Maximum size subset with given sum | A Dynamic Programming solution for subset sum problem + maximal subset value . Returns size of maximum sized subset if there is a subset of set [ ] with sun equal to given sum . It returns - 1 if there is no subset with 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 ; Driver code
def isSubsetSum ( arr , n , sum ) : NEW_LINE INDENT subset = [ [ False for x in range ( n + 1 ) ] for y in range ( sum + 1 ) ] NEW_LINE count = [ [ 0 for x in range ( n + 1 ) ] for y in range ( sum + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT subset [ 0 ] [ i ] = True NEW_LINE count [ 0 ] [ i ] = 0 NEW_LINE DEDENT for i in range ( 1 , sum + 1 ) : NEW_LINE INDENT subset [ i ] [ 0 ] = False NEW_LINE count [ i ] [ 0 ] = - 1 NEW_LINE DEDENT for i in range ( 1 , sum + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT subset [ i ] [ j ] = subset [ i ] [ j - 1 ] NEW_LINE count [ i ] [ j ] = count [ i ] [ j - 1 ] NEW_LINE if ( i >= arr [ j - 1 ] ) : NEW_LINE INDENT subset [ i ] [ j ] = ( subset [ i ] [ j ] or subset [ i - arr [ j - 1 ] ] [ j - 1 ] ) NEW_LINE if ( subset [ i ] [ j ] ) : NEW_LINE INDENT count [ i ] [ j ] = ( max ( count [ i ] [ j - 1 ] , count [ i - arr [ j - 1 ] ] [ j - 1 ] + 1 ) ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return count [ sum ] [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 3 , 5 , 10 ] NEW_LINE sum = 20 NEW_LINE n = 4 NEW_LINE print ( isSubsetSum ( arr , n , sum ) ) NEW_LINE DEDENT