Count of Ways to obtain given Sum from the given Array elements | Java Program to implement the above approach ; 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
import java . io . * ; import java . util . * ; class GFG { static int findWays ( int [ ] nums , int S ) { int sum = 0 ; for ( int i = 0 ; i < nums . length ; i ++ ) sum += nums [ i ] ; int [ ] [ ] memo = new int [ nums . length + 1 ] [ 2 * sum + 1 ] ; for ( int [ ] m : memo ) { Arrays . fill ( m , Integer . MIN_VALUE ) ; } return dfs ( memo , nums , S , 0 , 0 , sum ) ; } static int dfs ( int [ ] [ ] memo , int [ ] nums , int S , int curr_sum , int index , int sum ) { if ( index == nums . length ) { if ( S == curr_sum ) return 1 ; else return 0 ; } if ( memo [ index ] [ curr_sum + sum ] != Integer . MIN_VALUE ) { return memo [ index ] [ curr_sum + sum ] ; } int 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 ; } public static void main ( String [ ] args ) { int S = 3 ; int [ ] arr = new int [ ] { 1 , 2 , 3 , 4 , 5 } ; int answer = findWays ( arr , S ) ; System . out . println ( answer ) ; } }