Number of subsets with zero sum | Java implementation of above approach ; 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
class GFG { static int maxSum = 100 ; static int arrSize = 51 ; static int [ ] [ ] dp = new int [ arrSize ] [ maxSum ] ; static boolean [ ] [ ] visit = new boolean [ arrSize ] [ maxSum ] ; static 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 + arrSize ] ) { return dp [ i ] [ s + arrSize ] ; } visit [ i ] [ s + arrSize ] = true ; dp [ i ] [ s + arrSize ] = SubsetCnt ( i + 1 , s + arr [ i ] , arr , n ) + SubsetCnt ( i + 1 , s , arr , n ) ; return dp [ i ] [ s + arrSize ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 2 , 2 , - 4 , - 4 } ; int n = arr . length ; System . out . println ( SubsetCnt ( 0 , 0 , arr , n ) ) ; } }