Count of subsets with sum equal to X | Javascript implementation of the approach ; To store the states of DP ; Function to return the required count ; Base case ; If the state has been solved before return the value of the state ; Setting the state as solved ; Recurrence relation ; Driver code
var maxN = 20 var maxSum = 50 var minSum = 50 var base = 50 var dp = Array . from ( Array ( maxN ) , ( ) => Array ( maxSum + minSum ) ) ; var v = Array . from ( Array ( maxN ) , ( ) => Array ( maxSum + minSum ) ) ; function findCnt ( arr , i , required_sum , n ) { if ( i == n ) { if ( required_sum == 0 ) return 1 ; else return 0 ; } if ( v [ i ] [ required_sum + base ] ) return dp [ i ] [ required_sum + base ] ; v [ i ] [ required_sum + base ] = 1 ; dp [ i ] [ required_sum + base ] = findCnt ( arr , i + 1 , required_sum , n ) + findCnt ( arr , i + 1 , required_sum - arr [ i ] , n ) ; return dp [ i ] [ required_sum + base ] ; } var arr = [ 3 , 3 , 3 , 3 ] ; var n = arr . length ; var x = 6 ; document . write ( findCnt ( arr , 0 , x , n ) ) ;