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