Perfect Sum Problem ( Print all subsets with given sum ) | C ++ program to count all subsets with given sum . ; dp [ i ] [ j ] is going to store true if sum j is possible with array elements from 0 to i . ; A recursive function to print all subsets with the help of dp [ ] [ ] . Vector p [ ] stores current subset . ; If we reached end and sum is non - zero . We print p [ ] only if arr [ 0 ] is equal to sun OR dp [ 0 ] [ sum ] is true . ; Display Only when Sum of elements of p is equal to sum ; If sum becomes 0 ; If given sum can be achieved after ignoring current element . ; Create a new vector to store path ; If given sum can be achieved after considering current element . ; Prints all subsets of arr [ 0. . n - 1 ] with sum 0. ; Sum 0 can always be achieved with 0 elements ; Sum arr [ 0 ] can be achieved with single element ; Fill rest of the entries in dp [ ] [ ] ; Now recursively traverse dp [ ] [ ] to find all paths from dp [ n - 1 ] [ sum ] ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool * * dp ; void display ( const vector < int > & v ) { for ( int i = 0 ; i < v . size ( ) ; ++ i ) printf ( " % d ▁ " , v [ i ] ) ; printf ( " STRNEWLINE " ) ; } void printSubsetsRec ( int arr [ ] , int i , int sum , vector < int > & p ) { if ( i == 0 && sum != 0 && dp [ 0 ] [ sum ] ) { p . push_back ( arr [ i ] ) ; if ( arr [ i ] == sum ) display ( p ) ; return ; } if ( i == 0 && sum == 0 ) { display ( p ) ; return ; } if ( dp [ i - 1 ] [ sum ] ) { vector < int > b = p ; printSubsetsRec ( arr , i - 1 , sum , b ) ; } if ( sum >= arr [ i ] && dp [ i - 1 ] [ sum - arr [ i ] ] ) { p . push_back ( arr [ i ] ) ; printSubsetsRec ( arr , i - 1 , sum - arr [ i ] , p ) ; } } void printAllSubsets ( int arr [ ] , int n , int sum ) { if ( n == 0 sum < 0 ) return ; dp = new bool * [ n ] ; for ( int i = 0 ; i < n ; ++ i ) { dp [ i ] = new bool [ sum + 1 ] ; dp [ i ] [ 0 ] = true ; } if ( arr [ 0 ] <= sum ) dp [ 0 ] [ arr [ 0 ] ] = true ; for ( int i = 1 ; i < n ; ++ i ) for ( int j = 0 ; j < sum + 1 ; ++ j ) dp [ i ] [ j ] = ( arr [ i ] <= j ) ? dp [ i - 1 ] [ j ] || dp [ i - 1 ] [ j - arr [ i ] ] : dp [ i - 1 ] [ j ] ; if ( dp [ n - 1 ] [ sum ] == false ) { printf ( " There ▁ are ▁ no ▁ subsets ▁ with ▁ sum ▁ % d STRNEWLINE " , sum ) ; return ; } vector < int > p ; printSubsetsRec ( arr , n - 1 , sum , p ) ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int sum = 10 ; printAllSubsets ( arr , n , sum ) ; return 0 ; }