Count number of paths whose weight is exactly X and has at | C # program to count the number of paths ; Function to find the number of paths ; If the summation is more than X ; If exactly X weights have reached ; Already visited ; Count paths ; Traverse in all paths ; If the edge weight is M ; else Edge 's weight is not M ; Driver Code ; Initialized the DP array with - 1 ; Function to count paths
using System ; class GFG { static int max = 4 ; static int c = 2 ; static int countPaths ( int sum , int get , int m , int n , int [ , ] dp ) { if ( sum < 0 ) return 0 ; if ( sum == 0 ) return get ; if ( dp [ sum , get ] != - 1 ) return dp [ sum , get ] ; int res = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( i == m ) res += countPaths ( sum - i , 1 , m , n , dp ) ; res += countPaths ( sum - i , get , m , n , dp ) ; } dp [ sum , get ] = res ; return dp [ sum , get ] ; } public static void Main ( ) { int n = 3 , m = 2 , x = 3 ; int [ , ] dp = new int [ max + 1 , 2 ] ; for ( int i = 0 ; i <= max ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) dp [ i , j ] = - 1 ; Console . WriteLine ( countPaths ( x , 0 , m , n , dp ) ) ; } }