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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define max  4 NEW_LINE #define c  2 NEW_LINE 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 ] ; } int main ( ) { int n = 3 , m = 2 , x = 3 ; int dp [ max + 1 ] ; for ( int i = 0 ; i <= max ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) dp [ i ] [ j ] = -1 ; cout << countPaths ( x , 0 , m , n , dp ) ; }