Count of Ways to obtain given Sum from the given Array elements | 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
def knapSack ( nums , S ) : NEW_LINE INDENT sum = 0 ; NEW_LINE for i in range ( len ( nums ) ) : NEW_LINE INDENT sum += nums [ i ] ; NEW_LINE DEDENT if ( sum < S or - sum > - S or ( S + sum ) % 2 == 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT dp = [ 0 ] * ( ( ( S + sum ) // 2 ) + 1 ) ; NEW_LINE dp [ 0 ] = 1 ; NEW_LINE for j in range ( len ( nums ) ) : NEW_LINE INDENT for i in range ( len ( dp ) - 1 , nums [ j ] - 1 , - 1 ) : NEW_LINE INDENT dp [ i ] += dp [ i - nums [ j ] ] ; NEW_LINE DEDENT DEDENT return dp [ len ( dp ) - 1 ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = 3 ; NEW_LINE arr = [ 1 , 2 , 3 , 4 , 5 ] ; NEW_LINE answer = knapSack ( arr , S ) ; NEW_LINE print ( answer ) ; NEW_LINE DEDENT