Count of Ways to obtain given Sum from the given Array elements | C ++ program to implement the above approach ; Function to call dfs to calculate the number of ways ; If target + sum is odd or S exceeds sum ; No sultion exists ; Return the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int knapSack ( int nums [ ] , int S , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += nums [ i ] ; if ( sum < S || - sum > - S || ( S + sum ) % 2 == 1 ) return 0 ; int dp [ ( S + sum ) / 2 + 1 ] ; for ( int i = 0 ; i <= ( S + sum ) / 2 ; i ++ ) dp [ i ] = 0 ; dp [ 0 ] = 1 ; for ( int j = 0 ; j < n ; j ++ ) { for ( int i = ( S + sum ) / 2 ; i >= nums [ j ] ; i -- ) { dp [ i ] += dp [ i - nums [ j ] ] ; } } return dp [ ( S + sum ) / 2 ] ; } int main ( ) { int S = 3 ; int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int answer = knapSack ( arr , S , 5 ) ; cout << answer << endl ; }