Number of Paths of Weight W in a K | Java 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
class GFG { public static int solve ( int [ ] [ ] dp , int wt , int K , int M , int used ) { if ( wt < 0 ) { return 0 ; } if ( wt == 0 ) { if ( used == 1 ) { 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 ; } public static void main ( String [ ] args ) { int W = 3 , K = 3 , M = 2 ; int [ ] [ ] dp = new int [ W + 1 ] [ 2 ] ; for ( int i = 0 ; i < W + 1 ; i ++ ) { for ( int j = 0 ; j < 2 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } System . out . print ( solve ( dp , W , K , M , 0 ) + "NEW_LINE"); } }