Find all distinct subset ( or subsequence ) sums of an array | Uses Dynamic Programming to find distinct subset Sums ; dp [ i ] [ j ] would be true if arr [ 0. . i - 1 ] has a subset with Sum equal to j . ; There is always a subset with 0 Sum ; Fill dp [ ] [ ] in bottom up manner ; Sums that were achievable without current array element ; Print last row elements ; Driver code
def printDistSum ( arr , n ) : NEW_LINE INDENT Sum = sum ( arr ) NEW_LINE dp = [ [ False for i in range ( Sum + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = True NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ arr [ i - 1 ] ] = True NEW_LINE for j in range ( 1 , Sum + 1 ) : NEW_LINE INDENT if ( dp [ i - 1 ] [ j ] == True ) : NEW_LINE INDENT dp [ i ] [ j ] = True NEW_LINE dp [ i ] [ j + arr [ i - 1 ] ] = True NEW_LINE DEDENT DEDENT DEDENT for j in range ( Sum + 1 ) : NEW_LINE INDENT if ( dp [ n ] [ j ] == True ) : NEW_LINE INDENT print ( j , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT arr = [ 2 , 3 , 4 , 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE printDistSum ( arr , n ) NEW_LINE