text: Number of paths with exactly k coins | A Naive Recursive c # program to count paths with exactly ' k ' coins ; Recursive function to count paths with sum k from ( 0 , 0 ) to ( m , n ) ; Base cases ; ( m , n ) can be reached either through ( m - 1 , n ) or through ( m , n - 1 ) ; A wrapper over pathCountRec ( ) ; Driver code
code: using System ; public class GFG { public const int R = 3 ; public const int C = 3 ; public static int pathCountRec ( int [ ] [ ] mat , int m , int n , int k ) { if ( m < 0 n < 0 ) { return 0 ; } if ( m == 0 && n == 0 && ( k == mat [ m ] [ n ] ) ) { return 1 ; } return pathCountRec ( mat , m - 1 , n , k - mat [ m ] [ n ] ) + pathCountRec ( mat , m , n - 1 , k - mat [ m ] [ n ] ) ; } public static int pathCount ( int [ ] [ ] mat , int k ) { return pathCountRec ( mat , R - 1 , C - 1 , k ) ; } public static void Main ( string [ ] args ) { int k = 12 ; int [ ] [ ] mat = new int [ ] [ ] { new int [ ] { 1 , 2 , 3 } , new int [ ] { 4 , 6 , 5 } , new int [ ] { 3 , 2 , 1 } } ; Console . WriteLine ( pathCount ( mat , k ) ) ; } }