> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/count-number-of-ways-to-partition-a-set-into-k-subsets.md).

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

Given two numbers n and k where n represents a number of elements in a set, find a 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}}
```

```java
class Solution {
    public int countP(int n, int k) {
        if (k > n)
            return 0;
        int[][] dp = new int[n + 1][k + 1];
        // dp[i][j] -> number of ways to partition into j subsets from a set of size i
        // Base cases
        for (int i = 1; i <= n; i++) {
            if (i <= k)
                dp[i][i] = 1;
            dp[i][1] = 1;
        }
        // Filling dp table like this to use our base cases
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k && j < i; j++) {
                dp[i][j] = k * dp[i - 1][k] + dp[i - 1][k - 1];
            }
        }
        return dp[n][k];
    }
}
```