Count of Ways to obtain given Sum from the given Array elements | C ++ program to implement the above approach ; 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 ; Function to call dfs ( ) to calculate the number of ways ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dfs ( int nums [ ] , int S , int curr_sum , int index , int n ) { if ( index == n ) { if ( S == curr_sum ) return 1 ; else return 0 ; } return dfs ( nums , S , curr_sum + nums [ index ] , index + 1 , n ) + dfs ( nums , S , curr_sum - nums [ index ] , index + 1 , n ) ; } int findWays ( int nums [ ] , int S , int n ) { return dfs ( nums , S , 0 , 0 , n ) ; } int main ( ) { int S = 3 ; int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int answer = findWays ( arr , S , n ) ; cout << ( answer ) ; return 0 ; }