In this problem you are given an integer n and k, where n represents number of elements and k represents number of subsets.
All you have to do is to partition n elements in k subsets and print all such configurations.
Note:
Check out the question video and write the recursive code as it is intended without changing signature. The judge can't force you but intends you to teach a concept.
As the given input implies that n = 3 and k = 2, which means we have to partition 3 elements (1, 2, 3) in 2 subsets. So there are 3 ways to do so which are shown in output.
Also remember that you can't print permutations. Like [2,1][3], [3][1,2] and [3][2,1] are the possible permutations for the first output i.e. [1,2][3].
And there can be no empty sets. Like [1, 2, 3][-] is an invalid option for output.
For more clarity of the question, watch this part of the video.
Approach:
Moving On
Let us go through the rules again:
Permutation in the partition is not allowed within the set and of the sets. For example if [1,2][3] is an answer, then we would not consider [2,1][3] as a different answer and neither [3][1.2].
We must divide n into k sets (no empty set is allowed).
We will solve this question through recursion and backtracking:
We will have two options - whether to form a new group with the current n or to place n in any already present group.
If there are many empty groups, we will place n only in one new group (to avoid permutation).
Some of the base cases:
If (k > n); Ways of partitioning in this case is zero (Example - n = 2, k = 3, we cannot divide 2 elements in 3 sets, therefore the answer will be 0).
If (k = n); Ways of partitioning in this case is 1 (Example - n = 2, k = 2. We can form only one valid case: [1][2].
If (n = 0 || k = 0); Ways of partitioning in this case is 0.
If (k = 1): Ways of partitioning in this case is one.
Let's try to draw the recursion tree for n = 3 and k = 2, keeping the above
points into consideration:
At level-1, we have three sets and all of those are empty. So we have only
one way to add 1, which is we add 1 to one empty set and pass the rest of the
work to level-2.
At level-2, we have two sets and out of which one set is non empty
(contains 1) and the second one is empty. So we have two ways to add 2,
which is we either add 2 to the non empty set (with 1) or to the empty set and
pass the rest of the work to level-3.
At level-3, we have two options to explore; first is if 3 is added to the option
when 2 was added to the non empty set.
In this case, we have two sets and out of which one set is non empty (contains
1 and 2) and the second one is empty. So we have two ways to add 3, which is
we either add 3 to the non empty set (with 1 and 2) or to the empty set.
And in the second option; we have two sets as well and both of them are non
empty, one contains 1 and another contains 2. So we have two ways to add 3
which is we either add 3 to the first non empty set (with 1) or to the second
non empty set (with 2) and pass the rest of work to level-4.
At level-4, we have no more options to explore as n is 3 and we already
dealt with 3 in previous level. So here, we check which of the possible answers
is valid. First answer is invalid because one set is empty in this answer which
violates one of the rules. Rest other answers do not violate any rule therefore
they all are valid.
For more clarity of this part, watch this part of the video.
At level-4, we have no more options to explore as n is 3 and we already
dealt with 3 in previous level. So here, we check which of the possible answers
is valid. First answer is invalid because one set is empty in this answer which
violates one of the rules. Rest other answers do not violate any rule therefore
they all are valid.
Let's draw the recursion tree for n = 4 and k = 3 before moving to the code,
just like we did for n =3 and k = 2:
At level-1, we have three sets and all of them are empty. So we have only
one way to add 1, which is we add 1 to one empty set and pass the rest of the
work to level-2.
At level-2, we have three sets and out of which one set is non empty
(contains 1) and other two are empty. So we have two ways to add 2, which is
we either add 2 to the non empty set (with 1) or to one of the empty sets and
pass the rest of the work to level-3.
At level-3, we have two options to explore; first is if 3 is added to the option
when 2 was added to the non empty set.
In this case, we have three sets and out of which one set is non empty
(contains 1 and 2) and other two sets are empty. So we have two ways to add
3, which is we either add 3 to the non empty set (with 1 and 2) or to one of the
empty sets.
And in the second option; we have three sets as well and both of them are non
empty, one contains 1 and another contains 2. So we have three ways to add
3 which are adding 3 to the first non empty set (with 1) or to the second non
empty set (with 2) or to the third empty; then pass the rest of work to level-4.
At level-4, we have five options to explore.
In the first case, we have three sets and out of which one set is non empty
(contains 1, 2 and 3) and the other two sets are empty. So we have two ways
to add 4, which is we either add 4 to the non empty set (with 1, 2 and 3) or to
one of the empty sets.
In the second option; we have three sets as well and two out of them are non
empty, one contains 1 and 2 and another contains 3. So we have three ways
to add 4 which are adding 4 to the first non empty set (with 1 and 2) or to the
second non empty set (with 3) or to the third empty set.
In the third option; we have three sets as well and two out of them are non
empty, one contains 1 and 3 and another contains 2. So we have three ways
to add 4 which are adding 4 to the first non empty set (with 1 and 3) or to the
second non empty set (with 2) or to the third empty set.
In the fourth option; we have three sets as well and two out of them are non
empty, one contains 1 and another contains 2 and 3. So we have three ways
to add 4 which are adding 4 to the first non empty set (with 1) or to the
second non empty set (with 2 and 3) or to the third empty set.
In the fifth option; we have three sets as well and all of them are non empty,
the first one contains 1, the second one contains 2 and the third one contains
3. So we have three ways to add 4 which are adding 4 to the first non empty
set (with 1) or to the second non empty set (with 2) or to the third non empty
set (with 3); then pass the rest of the work to level-4.
At level-5, we have no more options to explore as n is 4 and we already
dealt with 4 in previous level. So here, we check which of the possible answers
is valid. An answer is invalid if even one set is empty; which violates one of the
rules. If answers do not violate any rule then they are valid.
For more clarity of this part, watch this part of the video.
Signature of the function:
public static void solution (int i, int n, int k, int rssf, ArrayList & lt; ArrayList ans >)
i: current level
n: total levels
rssf: count of relevant sets so far. It stores the count of sets that have been
filled so far.
K: number of sets that we want.
ans: ArrayList of size k that stores the answer till that level.
Let's try to code this!
Code Explained!
Initially i is 0, rssf is 0 and ans is an empty arraylist of size k.
If (n - 1) elements can be divided into k sets, then the nth element can join
any of the kth sets. If n-1 elements can be divided into k - 1 sets, then the
nth element only has one choice and that is to make a new set.
We have to consider two cases at every level:
Case 1: to make a new set.
Case 2: to add the current element to any of the already present sets.
We use a FOR loop at every level. If the size of the ArrayList for the jth set is
zero, it means that jth set is empty, then we add i to that set (make a new
set) and break out of the loop as size of all the set after that will be zero and
to avoid permutations, we break (Case 1). As the number of sets is
increased in this case, therefore, we will increase rssf in this case.
If the size of the jth set is not zero, we add i to that set (Case2). As the
number of sets remains constant, we would not increase rssf.
In pre-order we add the i to the jth set and in post-order we remove it.
For the base case we check if i is greater than n, it means we have placed all
the elements. Then we will check if rssf is equal to the k, we will print the
answer in the required format. We will return after that.
For more clarity of the code, watch this part of the video.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int k = scn.nextInt();
ArrayList< ArrayList < Integer>> ans = new ArrayList<>();
for(int i = 0; i < k; i++) {
ans.add(new ArrayList<>());
}
solution(1, n, k, 0, ans);
}
static int counter = 1;
public static void solution(int i, int n, int k, int rssf, ArrayList< ArrayList< Integer>> ans) {
if (i == n + 1) {
if (rssf == k) {
System.out.print(counter + ". ");
counter++;
for(ArrayList< Integer> a : ans) {
System.out.print(a + " ");
}
System.out.println();
}
return;
}
for(int j = 0 ; j < ans.size(); j++) {
if(ans.get(j).size() == 0) {
ans.get(j).add(i);
solution(i + 1,n,k,rssf + 1,ans);
ans.get(j).remove(ans.get(j).size() - 1);
break;
}else {
ans.get(j).add(i);
solution(i + 1, n, k, rssf, ans);
ans.get(j).remove(ans.get(j).size() - 1);
}
}
}
}
java;
true";
Analysis
Time Complexity: O()
Space Complexity: O()
We hope that this article was helpful. If somehow you are finding it difficult to
understand this problem then we advise you to watch our
video lecture of this problem.
Trust me it will just get easier to understand after you have watched the
solution video.
You can contact us via our website. Doubts, suggestions and feedback are
always welcomed.
It is also advised that you follow the sequence of modules and questions
which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step
of each problem.
