Count of Ways to obtain given Sum from the given Array elements | Function to call dfs to calculate the number of ways ; Iterate till the length of array ; Initialize the memorization table ; Function to perform the DFS to calculate the number of ways ; Base case : Reached the end of array ; If current sum is obtained ; Otherwise ; If previously calculated subproblem occurred ; Check if the required sum can be obtained by adding current element or by subtracting the current index element ; Store the count of ways ; Driver Code
function findWays ( nums , S ) { let sum = 0 ; for ( let i = 0 ; i < nums . length ; i ++ ) sum += nums [ i ] ; let memo = new Array ( [ nums . length + 1 ] [ 2 * sum + 1 ] ) ; for ( let i = 0 ; i < nums . length + 1 ; i ++ ) { memo [ i ] = new Array ( 2 * sum + 1 ) ; for ( let j = 0 ; j < 2 * sum + 1 ; j ++ ) { memo [ i ] [ j ] = Number . MIN_VALUE ; } } return dfs ( memo , nums , S , 0 , 0 , sum ) ; } function dfs ( memo , nums , S , curr_sum , index , sum ) { if ( index == nums . length ) { if ( S == curr_sum ) return 1 ; else return 0 ; } if ( memo [ index ] [ curr_sum + sum ] != Number . MIN_VALUE ) { return memo [ index ] [ curr_sum + sum ] ; } let ans = dfs ( memo , nums , index + 1 , curr_sum + nums [ index ] , S , sum ) + dfs ( memo , nums , index + 1 , curr_sum - nums [ index ] , S , sum ) ; memo [ index ] [ curr_sum + sum ] = ans ; return ans ; } let S = 3 ; let arr = [ 1 , 2 , 3 , 4 , 5 ] ; let answer = findWays ( arr , S ) ; document . write ( answer ) ;