Coin Change | DP | Recursive JAVA 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
import java . util . * ; class GFG { static 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 ] ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 2 , 3 } ; int m = arr . length ; System . out . println ( count ( arr , m , 4 ) ) ; } }