Count number of paths whose weight is exactly X and has at | Python3 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
Max = 4 NEW_LINE c = 2 NEW_LINE def countPaths ( Sum , get , m , n , dp ) : NEW_LINE INDENT if ( Sum < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( Sum == 0 ) : NEW_LINE INDENT return get NEW_LINE DEDENT if ( dp [ Sum ] [ get ] != - 1 ) : NEW_LINE INDENT return dp [ Sum ] [ get ] NEW_LINE DEDENT res = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( i == m ) : NEW_LINE INDENT res += countPaths ( Sum - i , 1 , m , n , dp ) NEW_LINE res += countPaths ( Sum - i , get , m , n , dp ) NEW_LINE DEDENT DEDENT dp [ Sum ] [ get ] = res NEW_LINE return dp [ Sum ] [ get ] NEW_LINE DEDENT n = 3 NEW_LINE m = 2 NEW_LINE x = 3 NEW_LINE dp = [ [ - 1 for i in range ( 2 ) ] for i in range ( Max + 1 ) ] NEW_LINE for i in range ( Max + 1 ) : NEW_LINE INDENT for j in range ( 2 ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT print ( countPaths ( x , 0 , m , n , dp ) ) NEW_LINE