Find all distinct subset ( or subsequence ) sums of an array | Set | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void subsetSum ( int arr [ ] , int n , int maxSum ) { bool dp [ maxSum + 1 ] ; memset ( dp , false , sizeof dp ) ; dp [ arr [ 0 ] ] = true ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = maxSum + 1 ; j >= 1 ; j -- ) { if ( arr [ i ] <= j ) { if ( arr [ i ] == j || dp [ j ] || dp [ ( j - arr [ i ] ) ] ) dp [ j ] = true ; else dp [ j ] = false ; } } } cout << 0 << " ▁ " ; for ( int j = 0 ; j <= maxSum + 1 ; j ++ ) { if ( dp [ j ] == true ) cout << j << " ▁ " ; } } void printDistinct ( int a [ ] , int n ) { int maxSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { maxSum += a [ i ] ; } subsetSum ( a , n , maxSum ) ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 5 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printDistinct ( arr , n ) ; return 0 ; }