Programming is a skill best acquired by practice and examples rather than books.
Partition Into Subsets
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.
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. 1-2-34 1-23-4 12-3-4 13-2-4 14-2-3 1-24-3
P.S A set cannot be empty like 12-34-. is not a valid partition.
Approach :
Time Complexity: O(n*k)
Space Complexity: O(n*k)
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 .
Let's try to solve this for a bigger problem. N=5 and K=4. Since we have two states we clearly need 2-D dp. So, let's create one. Here dp[k][n] will store the number of ways to partition n numbers into k non-empty subsets. 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[2][1] Clearly, k>n so 0
Now dp[2][2] Clearly k==n so 1.
Now dp[2][3]. Here n>k. So we know
dp[2][3] = 2*dp[2][2] + dp[1][2] = 2*1 + 1 = 3
Now for dp[2][4] Again n>k So we use
dp[2][4] = 2*dp[2][3] + d[1][3] = 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.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int k = scn.nextInt();
if (n == 0 || k == 0 || n < k) {
System.out.println(0);
scn.close();
return;
}
long[][] dp = new long[k + 1][n + 1];
for (int t = 1; t <= k; t++) {
for (int p = 1; p <= n; p++) {
if (p == t)
dp[t][p] = 1;
else if (p > t)
dp[t][p] = t * dp[t][p - 1] + dp[t - 1][p - 1];
}
}
System.out.println(dp[k][n]);
scn.close();
}
}
java;
true";
Analysis:
Time Complexity:
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).
Space Complexity:
We are using a 2D grid of size n*k. Hence the space complexity is also O(n*k).