Dear reader, this is very similar to the previous question: Friends pairs. So, if you haven't completed that problem I would suggest you do that first. And if you have, take a stab at this problem and see if you are able to come up with a solution. Let's understand the problem.
Partition Into Subsets
Programming is a skill best acquired by practice and examples rather than books.
- You are given a number n, representing the number of elements.
- You are given a number k, representing the number of subsets.
- You are required to print the number of ways in which these elements can be partitioned in k non-empty subsets.
For example, If we have n=4,1234 and we want to divide it into 3 subsets we can do it these ways.
P.S A set cannot be empty like 12-34-. is not a valid partition.
Let's take a smaller example to understand our problem. Let n=3 and k=2.
Let's say we want to know first how n=2 numbers can be partitioned into k=2 subsets. Let's say it is x. Now what we can do is add 3 to any subset in each of the x partitions. That way we will now have n=3 numbers partitioned into 2 subsets.
Also, we can do it another way. Now we ask how to partition n=2 numbers but in k=1 subsets. Let's say it is y. Now we can just make 3 separate sets and add them to those y partitions. Since all the y partitions had k-1 sets adding 3 separately will make it k.
Clearly, this is very similar to the previous problem. Now, what are the total count = 2*x + y. In a more generic manner if f(n, k) is the count of the partitions of n into k subsets then we can represent it as: f(n, k) = (k)*f(n-1, k) + f(n-1, k-1)
If you had any difficulty understanding this part watch the video .
First, let's fill up the trivial cases. Now N=0 and K=0 don't make any sense at all so we can put 0 there.
Now no matter what n is if we have to partition it into 1 subset there is just 1 way hence for all n, k=1 the value will 1 too.
Another situation is when k>n, we literally can never make k non-empty partitions with n numbers. So those will be 0. Also if n==k then there is just one way to implement it. Each subset with 1 number.
But in all other cases, we will use our recursive formula. So let's do it, dp Clearly, k>n so 0
Now dp Clearly k==n so 1.
Now dp. Here n>k. So we know dp = 2*dp + dp = 2*1 + 1 = 3
Now for dp Again n>k So we use dp = 2*dp + d = 2*3 + 1 = 7
I would insist you complete the grid yourself. If you are stuck watch the video.
Once done, try to code it yourself. If you are stuck you can see the code below.
Simple two loops are running. The outer loop is k times. The inner loop is n times. Hence the time complexity is O(k*n).
We are using a 2D grid of size n*k. Hence the space complexity is also O(n*k).