text: Number of Paths of Weight W in a K | C ++ program to count the number of paths with weight W in a K - ary tree ; Function to return the number of ways having weight as wt in K - ary tree ; Return 0 if weight becomes less than zero ; Return one only if the current path has included edge weight of atleast M ; If the current edge weight is greater than or equal to M , set used as true ; Driver Code to test above function
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( int dp [ ] [ 2 ] , int wt , int K , int M , int used ) { if ( wt < 0 ) return 0 ; if ( wt == 0 ) { if ( used ) return 1 ; return 0 ; } if ( dp [ wt ] [ used ] != -1 ) return dp [ wt ] [ used ] ; int ans = 0 ; for ( int i = 1 ; i <= K ; i ++ ) { if ( i >= M ) ans += solve ( dp , wt - i , K , M , used 1 ) ; else ans += solve ( dp , wt - i , K , M , used ) ; } return dp [ wt ] [ used ] = ans ; } int main ( ) { int W = 3 , K = 3 , M = 2 ; int dp [ W + 1 ] [ 2 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << solve ( dp , W , K , M , 0 ) << endl ; return 0 ; }