text: Number of subsets with zero sum |  ; variable to store states of dp ; To find the number of subsets with sum equal to 0 Since S can be negative , we will maxSum to it to make it positive ; Base cases ; Returns the value if a state is already solved ; If the state is not visited , then continue ; Recurrence relation ; Returning the value ; Driver function
code: #include <bits/stdc++.h> NEW_LINE #define maxSum  100 NEW_LINE #define arrSize  51 NEW_LINE using namespace std ; int dp [ arrSize ] [ maxSum ] ; bool visit [ arrSize ] [ maxSum ] ; int SubsetCnt ( int i , int s , int arr [ ] , int n ) { if ( i == n ) { if ( s == 0 ) return 1 ; else return 0 ; } if ( visit [ i ] [ s + maxSum ] ) return dp [ i ] [ s + maxSum ] ; visit [ i ] [ s + maxSum ] = 1 ; dp [ i ] [ s + maxSum ] = SubsetCnt ( i + 1 , s + arr [ i ] , arr , n ) + SubsetCnt ( i + 1 , s , arr , n ) ; return dp [ i ] [ s + maxSum ] ; } int main ( ) { int arr [ ] = { 2 , 2 , 2 , -4 , -4 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << SubsetCnt ( 0 , 0 , arr , n ) ; }