Count of Ways to obtain given Sum from the given Array elements | C ++ Program to implement the above approach ; 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 ; Function to call dfs to calculate the number of ways ; Iterate till the length of array ; Initialize the memorization table ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dfs ( vector < vector < int > > memo , int nums [ ] , int S , int curr_sum , int index , int sum , int N ) { if ( index == N ) { if ( S == curr_sum ) return 1 ; else return 0 ; } if ( memo [ index ] [ curr_sum + sum ] != INT_MIN ) { return memo [ index ] [ curr_sum + sum ] ; } int ans = dfs ( memo , nums , index + 1 , curr_sum + nums [ index ] , S , sum , N ) + dfs ( memo , nums , index + 1 , curr_sum - nums [ index ] , S , sum , N ) ; memo [ index ] [ curr_sum + sum ] = ans ; return ans ; } int findWays ( int nums [ ] , int S , int N ) { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += nums [ i ] ; vector < vector < int > > memo ( N + 1 , vector < int > ( 2 * sum + 1 , INT_MIN ) ) ; return dfs ( memo , nums , S , 0 , 0 , sum , 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 << endl ; return 0 ; }