Count the number of ways to divide N in k groups incrementally | C # implementation to count the number of ways to divide N in groups such that each group has K number of elements ; DP Table ; Function to count the number of ways to divide the number N in groups such that each group has K number of elements ; Base Case ; if N is divides completely into less than k groups ; If the subproblem has been solved , use the value ; put all possible values greater equal to prev ; Function to count the number of ways to divide the number N in groups ; Initialize DP Table as - 1 ; Driver Code
using System ; class GFG { static int [ , , ] dp = new int [ 50 , 50 , 50 ] ; static int calculate ( int pos , int prev , int left , int k ) { if ( pos == k ) { if ( left == 0 ) return 1 ; else return 0 ; } if ( left == 0 ) return 0 ; if ( dp [ pos , prev , left ] != - 1 ) return dp [ pos , prev , left ] ; int answer = 0 ; for ( int i = prev ; i <= left ; i ++ ) { answer += calculate ( pos + 1 , i , left - i , k ) ; } return dp [ pos , prev , left ] = answer ; } static int countWaystoDivide ( int n , int k ) { for ( int i = 0 ; i < 50 ; i ++ ) { for ( int j = 0 ; j < 50 ; j ++ ) { for ( int l = 0 ; l < 50 ; l ++ ) dp [ i , j , l ] = - 1 ; } } return calculate ( 0 , 1 , n , k ) ; } public static void Main ( String [ ] args ) { int N = 8 ; int K = 4 ; Console . Write ( countWaystoDivide ( N , K ) ) ; } }