text: Coin Change | DP | Recursive C ++ program for coin change problem . ; 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 code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int count ( int S [ ] , int m , int n ) { if ( n == 0 ) return 1 ; if ( n < 0 ) return 0 ; if ( m <= 0 && n >= 1 ) return 0 ; return count ( S , m - 1 , n ) + count ( S , m , n - S [ m - 1 ] ) ; } int main ( ) { int i , j ; int arr [ ] = { 1 , 2 , 3 } ; int m = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " ▁ " << count ( arr , m , 4 ) ; return 0 ; }