Coin Change | DP | Returns the count of ways we can sum S [ 0. . . m - 1 ] coins to get sum n ; If n is 0 then there is 1 solution ( do not include any coin ) ; If n is less than 0 then no solution exists ; If there are no coins and n is greater than 0 , then no solution exist ; count is sum of solutions ( i ) including S [ m - 1 ] ( ii ) excluding S [ m - 1 ] ; Driver program to test above function
def count ( S , m , n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( n < 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( m <= 0 and n >= 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return count ( S , m - 1 , n ) + count ( S , m , n - S [ m - 1 ] ) ; NEW_LINE DEDENT arr = [ 1 , 2 , 3 ] NEW_LINE m = len ( arr ) NEW_LINE print ( count ( arr , m , 4 ) ) NEW_LINE