Find all distinct subset ( or subsequence ) sums of an array | Set | Java program to find total sum of all distinct subset sums in O ( sum ) space . ; 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
import java . util . * ; class Main { public static void subsetSum ( int arr [ ] , int n , int maxSum ) { boolean dp [ ] = new boolean [ maxSum + 1 ] ; Arrays . fill ( dp , false ) ; dp [ arr [ 0 ] ] = true ; for ( int i = 1 ; i < n ; i ++ ) { for ( int 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 ; } } } System . out . print ( 0 + " ▁ " ) ; for ( int j = 0 ; j <= maxSum ; j ++ ) { if ( dp [ j ] == true ) System . out . print ( j + " ▁ " ) ; } System . out . print ( "21" ) ; } public static void printDistinct ( int a [ ] , int n ) { int maxSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { maxSum += a [ i ] ; } subsetSum ( a , n , maxSum ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 4 , 5 , 6 } ; int n = arr . length ; printDistinct ( arr , n ) ; } }