# Count number of ways to partition a set into k subsets

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.

Example:

```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}}

Input: n = 3, k = 1
Output: 1
Explanation: There is only one way {{1, 2, 3}}
```

We strongly recommend you to minimize your browser and try this yourself first.

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)

Below is recursive solution based on above formula.

## C++

 `// A C++ program to count number of partitions ` `// of a set with n elements into k subsets ` `#include ` `using` `namespace` `std; ` ` `  `// 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); ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `   ``cout <<  countP(3, 2); ` `   ``return` `0; ` `} `

## Java

 `// Java  program to count number  ` `// of partitions of a set with  ` `// n elements into k subsets ` `import` `java.io.*; ` ` `  `class` `GFG ` `{ ` `    ``// Returns count of different  ` `    ``// partitions of n elements in ` `    ``// k subsets ` `    ``public` `static` `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``)); ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `       ``System.out.println(countP(``3``, ``2``)); ` ` `  `    ``} ` `} ` ` `  `//This code is contributed by Anshika Goyal. `

## Python 3

 `# A Python3 program to count number ` `# of partitions of a set with n ` `# elements into k subsets ` ` `  `# Returns count of different partitions  ` `# of n elements in k subsets ` `def` `countP(n, k): ` `     `  `    ``# Base cases ` `    ``if` `(n ``=``=` `0` `or` `k ``=``=` `0` `or` `k > n): ` `        ``return` `0` `    ``if` `(k ``=``=` `1` `or` `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``)) ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``print``(countP(``3``, ``2``)) ` ` `  `# This code is contributed  ` `# by Akanksha Rai(Abby_akku) `

## C#

 `// C# program to count number  ` `// of partitions of a set with  ` `// n elements into k subsets ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns count of different  ` `    ``// partitions of n elements in ` `    ``// k subsets ` `    ``public` `static` `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)); ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``Console.WriteLine(countP(3, 2)); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` ``\$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); ` `} ` ` `  `    ``// Driver Code ` `    ``echo` `countP(3, 2); ` ` `  `// This code is contributed by aj_36 ` `?> `

Output:

`3`

The time complexity of above recursive solution is exponential. The solution can be optimized as there are overlapping subproblems. For example, below is recursion tree of countP(10,7). The subproblem countP(8,6) or CP(8,6) is called multiple times.

``` CP() represents countP()

CP(10,7)
/
CP(9,7)       CP(9,6)
/           /
CP(8,7) CP(8,6) CP(8,6)  CP(8,5)
/     /      /        /

Partial Recursion Tree for countP(10, 7)
to highlight overlapping subproblems.
```

So this problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array dp[][] in bottom up manner using the above recursive formula.

Below is the implementation of Dynamic Programming Solution.

## C++

 `// A Dynamic Programming based C++ program to count ` `// number of partitions of a set with n elements ` `// into k subsets ` `#include ` `using` `namespace` `std; ` ` `  `// 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; ` `  ``for` `(``int` `i = 0; i <= k; i++) ` `     ``dp[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]; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `   ``cout <<  countP(5, 2); ` `   ``return` `0; ` `} `

## Java

 `// A Dynamic Programming based Java program to count  ` `// number of partitions of a set with n elements  ` `// into k subsets  ` `class` `GFG{ ` ` `  `// Returns count of different partitions of n  ` `// elements in k subsets  ` `static` `int` `countP(``int` `n, ``int` `k)  ` `{  ` `    ``// Table to store results of subproblems  ` `    ``int``[][] dp = ``new` `int``[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 <= k; 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];  ` `     `  `}  ` ` `  `// Driver program  ` `public` `static` `void` `main(String[] args )  ` `{  ` `    ``System.out.println(countP(``5``, ``2``));  ` `}  ` `} ` ` `  `// This code is contributed by Rajput-Ji `

## Python3

 `# A Dynamic Programming based Python3 program  ` `# to count number of partitions of a set with  ` `# n elements into k subsets ` ` `  `# Returns count of different partitions  ` `# of n elements in k subsets ` `def` `countP(n, k): ` `     `  `    ``# Table to store results of subproblems ` `    ``dp ``=` `[[``0` `for` `i ``in` `range``(k ``+` `1``)]  ` `             ``for` `j ``in` `range``(n ``+` `1``)] ` ` `  `    ``# Base cases ` `    ``for` `i ``in` `range``(n ``+` `1``): ` `        ``dp[i][``0``] ``=` `0` ` `  `    ``for` `i ``in` `range``(k ``+` `1``): ` `        ``dp[``0``][k] ``=` `0` ` `  `    ``# Fill rest of the entries in  ` `    ``# dp[][] in bottom up manner ` `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` `        ``for` `j ``in` `range``(``1``, k ``+` `1``): ` `            ``if` `(j ``=``=` `1` `or` `i ``=``=` `j): ` `                ``dp[i][j] ``=` `1` `            ``else``: ` `                ``dp[i][j] ``=` `(j ``*` `dp[i ``-` `1``][j] ``+` `                                ``dp[i ``-` `1``][j ``-` `1``]) ` `                 `  `    ``return` `dp[n][k] ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``print``(countP(``5``, ``2``)) ` ` `  `# This code is contributed by ` `# Surendra_Gangwar `

## C#

 `// A Dynamic Programming based C# program   ` `// to count number of partitions of a   ` `// set with n elements into k subsets  ` `using` `System; ` ` `  `class` `GFG ` `{ ` ` `  `// Returns count of different partitions of n  ` `// elements in k subsets  ` `static` `int` `countP(``int` `n, ``int` `k)  ` `{  ` `    ``// Table to store results of subproblems  ` `    ``int``[,] dp = ``new` `int``[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 <= k; 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];  ` `     `  `}  ` ` `  `// Driver code  ` `public` `static` `void` `Main( )  ` `{  ` `    ``Console.Write(countP(5, 2));  ` `}  ` `} ` ` `  `// This code is contributed by Ita_c. `

## PHP

 ` `

Output:

`15`

Time Complexity: O(n x k)
Auxiliary Space: O(n x k)

Similar Article: Bell Numbers