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 Code
< ? php function coun ( $ S , $ m , $ n ) { if ( $ n == 0 ) return 1 ; if ( $ n < 0 ) return 0 ; if ( $ m <= 0 && $ n >= 1 ) return 0 ; return coun ( $ S , $ m - 1 , $ n ) + coun ( $ S , $ m , $ n - $ S [ $ m - 1 ] ) ; } $ arr = array ( 1 , 2 , 3 ) ; $ m = count ( $ arr ) ; echo coun ( $ arr , $ m , 4 ) ; ? >