Count number of ways to partition a set into k subsets - GeeksforGeeks

Count number of ways to partition a set into k subsets - GeeksforGeeks
Given two numbers n and k where n represents number of elements in a set, find number of ways to partition the set into k subsets.

Input: n = 3, k = 2
Output: 3
Explanation: Let the set be {1, 2, 3}, we can partition
             it into 2 subsets in following ways
             {{1,2}, {3}},  {{1}, {2,3}},  {{1,3}, {2}}  

Let S(n, k) be total number of partitions of n elements into k sets. Value of S(n, k) can be defined recursively as,

S(n, k) = k*S(n-1, k) + S(n-1, k-1) 

S(n, k) is called Stirling numbers of the second kind

How does above recursive formula work?
When we add a (n+1)’th element to k partitions, there are two possibilities.
1) It is added as a single element set to existing partitions, i.e, S(n, k-1)
2) It is added to all sets of every partition, i.e., k*S(n, k)

Therefore S(n+1, k) = k*S(n, k) + S(n, k-1) which means S(n, k) = k*S(n-1, k) + S(n-1, k-1)

// Returns count of different partitions of n

// elements in k subsets

int countP(int n, int k)

{

  // Table to store results of subproblems

  int dp[n+1][k+1];

  // Base cases

  for (int i=0; i<=n; i++)

     dp[i][0] = 0;

  for (int i=0; i<=k; i++)

     dp[0][k] = 0;

  // Fill rest of the entries in dp[][]

  // in bottom up manner

  for (int i=1; i<=n; i++)

     for (int j=1; j<=i; j++)

       if (j == 1 || i == j)

          dp[i][j] = 1;

       else

          dp[i][j] = j*dp[i-1][j] + dp[i-1][j-1];

  return dp[n][k];

}

Recursive Version:

// Returns count of different partitions of n

// elements in k subsets

int countP(int n, int k)

{

  // Base cases

  if (n == 0 || k == 0 || k > n)

     return 0;

  if (k == 1 || k == n)

      return 1;

  // S(n+1, k) = k*S(n, k) + S(n, k-1)

  return  k*countP(n-1, k) + countP(n-1, k-1);

}

Read full article from Count number of ways to partition a set into k subsets - GeeksforGeeks