Kpartitions
1. You are given two integers n and k, where n represents number of elements and k representsInput Format
number of subsets.
2. You have 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.
A number nOutput Format
A number k
Check the sample ouput and question video.Question Video
1 <= n <= 10Sample Input
1 <= k <= 10
3Sample Output
2
1. [1, 2] [3]
2. [1, 3] [2]
3. [1] [2, 3]

Editorial
Let us go through the rules again. Permutation in partition is not allowed. For example if
(1  2) is an answer, then we would not consider (2  1) as a different answer. We must divide n into k sets.
We will solve this question through recursion and backtracking. We will place n at level.
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(to avoid permutation). Some of the base cases 
 k > n  Ways of partitioning in this case is zero (Example  n = 2, k = 3, we cannot divide 2 elements in 3 sets, therefore answer will be zero).
 k = n  Ways of partitioning in this case is 1 (Example  n = 2, k = 2. We can form only one valid case  1  2)
 n = 0  k = 0  Ways of partitioning in this case is 0.
 k = 1  Ways of partitioning in this case is one.
Signature:
public static void solution(int i, int n, int k, int rssf, ArrayList < ArrayList
ans) i  current level
n  total levels.
rssf  count of relevant set so far. It stores the count of set, 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.
Code:
static int counter = 1; public static void solution(int i, int n, int k, int rssf, ArrayList
> ans) { if (i == n + 1) { if (rssf == k) { System.out.print(counter + ". "); counter++; for(ArrayList
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 false
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 nth element can join any of the kth set. If n1 elements can be divided into k  1 sets, then 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 set.
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 set 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 preorder we add the i to the jth set and in postorder we remove it.
Base Case:
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.
Recursion Tree:
n = 4 and k = 3 for the following example.

Asked in Companies

Related Topics