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
function subsetSum ( arr , n , maxSum ) { var dp = Array ( maxSum + 1 ) . fill ( false ) dp [ arr [ 0 ] ] = true ; for ( var i = 1 ; i < n ; i ++ ) { for ( var j = maxSum ; j >= 1 ; j -- ) { if ( arr [ i ] <= j ) { if ( arr [ i ] == j || dp [ j ] || dp [ ( j - arr [ i ] ) ] ) dp [ j ] = true ; else dp [ j ] = false ; } } } document . write ( 0 + " " ) ; for ( var j = 0 ; j < maxSum + 1 ; j ++ ) { if ( dp [ j ] == true ) document . write ( j + " " ) ; } document . write ( " " ) ; } function printDistinct ( a , n ) { var maxSum = 0 ; for ( var i = 0 ; i < n ; i ++ ) { maxSum += a [ i ] ; } subsetSum ( a , n , maxSum ) ; } var arr = [ 2 , 3 , 4 , 5 , 6 ] ; var n = arr . length ; printDistinct ( arr , n ) ;