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 ; Function to count the number of ways ; Base Case : Reached the end of the array ; Sum is equal to the required sum ; Recursively check if required sum can be obtained by adding current element or by subtracting the current index element ; Driver Code
import java . io . * ; class GFG { static int findWays ( int [ ] nums , int S ) { return dfs ( nums , S , 0 , 0 ) ; } static int dfs ( int [ ] nums , int S , int curr_sum , int index ) { if ( index == nums . length ) { if ( S == curr_sum ) return 1 ; else return 0 ; } return dfs ( nums , S , curr_sum + nums [ index ] , index + 1 ) + dfs ( nums , S , curr_sum - nums [ index ] , index + 1 ) ; } 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 ) ; } }