Find all distinct subset ( or subsequence ) sums of an array | Set | Function to print all th distinct sum ; Declare a boolean array of size equal to total sum of the array ; Fill the first row beforehand ; dp [ j ] will be true only if sum j can be formed by any possible addition of numbers in given array upto index i , otherwise false ; Iterate from maxSum to 1 and avoid lookup on any other row ; Do not change the dp array for j less than arr [ i ] ; If dp [ j ] is true then print ; Function to find the total sum and print the distinct sum ; find the sum of array elements ; Function to print all the distinct sum ; Driver Code
def subsetSum ( arr , n , maxSum ) : NEW_LINE INDENT dp = [ False for i in range ( maxSum + 1 ) ] NEW_LINE dp [ arr [ 0 ] ] = True NEW_LINE for i in range ( 1 , n , 1 ) : NEW_LINE INDENT j = maxSum NEW_LINE while ( j >= 1 ) : NEW_LINE INDENT if ( arr [ i ] <= j ) : NEW_LINE INDENT if ( arr [ i ] == j or dp [ j ] or dp [ ( j - arr [ i ] ) ] ) : NEW_LINE INDENT dp [ j ] = True NEW_LINE DEDENT else : NEW_LINE INDENT dp [ j ] = False NEW_LINE DEDENT DEDENT j -= 1 NEW_LINE DEDENT DEDENT print ( 0 , end = " ▁ " ) NEW_LINE for j in range ( maxSum + 1 ) : NEW_LINE INDENT if ( dp [ j ] == True ) : NEW_LINE INDENT print ( j , end = " ▁ " ) NEW_LINE DEDENT DEDENT print ( "21" ) NEW_LINE DEDENT def printDistinct ( a , n ) : NEW_LINE INDENT maxSum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT maxSum += a [ i ] NEW_LINE DEDENT subsetSum ( a , n , maxSum ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE printDistinct ( arr , n ) NEW_LINE DEDENT