Redirecting to
NADOS

K-partitions

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

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

    1. 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).
    2. k = n - Ways of partitioning in this case is 1 (Example - n = 2, k = 2. We can form only one valid case - 1 | 2)
    3. n = 0  || k = 0 - Ways of partitioning in this case is 0.
    4. 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 n-1 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 pre-order we add the i to the jth set and in post-order 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






Video Solution

Code Solution

Run
 
Run
Id Name