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 ; If target + sum is odd or S exceeds sum ; No sultion exists ; Return the answer ; Driver Code
import java . io . * ; class GFG { static int knapSack ( int [ ] nums , int S ) { int sum = 0 ; for ( int i : nums ) sum += i ; if ( sum < S || - sum > - S || ( S + sum ) % 2 == 1 ) return 0 ; int [ ] dp = new int [ ( S + sum ) / 2 + 1 ] ; dp [ 0 ] = 1 ; for ( int num : nums ) { for ( int i = dp . length - 1 ; i >= num ; i -- ) { dp [ i ] += dp [ i - num ] ; } } return dp [ dp . length - 1 ] ; } public static void main ( String [ ] args ) { int S = 3 ; int [ ] arr = new int [ ] { 1 , 2 , 3 , 4 , 5 } ; int answer = knapSack ( arr , S ) ; System . out . println ( answer ) ; } }