Making mistakes is how we learn.
Don't be afraid to make mistakes.
Even the most seasoned developer has made these mistakes and learned from them.
K Subsets with Equal Sum
Welcome Back Reader!
In this article we will discuss about the next problem based on "Recursion and
Backtracking" i.e. K Subsets with Equal Sum.
If you have solved the problem K - Partitions
of this module, then you would
be happy to know that this problem is just an extension of that problem.
In that problem we were given two integers n and k and we had to partition
the n elements in k sets such that no set is empty.
We have to do exactly the same in this problem too. And just take an extra rule
into consideration that is we need to make sure that the sum of elements of
each subset is equal.
And if you haven't gone through that problem
then it is advised that you
should first go and understand that problem first for better grasp of this one.
Before you move any further, it is advised that you give this problem
a fair try.
Let's jump to the problem.
In this problem you are given an integer n which represents size of the array
and then n numbers more that represents n distinct integers of the array and
an integer k.
All you have to do is divide these n integers into k non - empty subsets such
that the sum of integers of every subset is the same. If it is not possible to
divide then print "-1".
Note: Check out the [00:00 - 02:30] part of the 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.
Sample Input: 6
1
2
3
4
5
6
3
Sample Output: [1, 6] [2, 5] [3, 4]
How ?
As the given input implies that n = 6, array[] = {1, 2, 3, 4, 5, 6} and k = 3,
which means we have to partition 6 elements of the array (1, 2, 3, 4, 5, 6) in
3 subsets such that sum of each subset is equal. So there is only one way to
do so which is shown in the output ([1, 6] [2, 5] [3, 4]).
Here also remember that you can't print permutations. Like ([6, 1] [2, 5] [3,
4]) is one of the possible permutations for the given output.
And there can be no empty sets. So any answer with an empty set is an
invalid option for output.
For more clarity of the question; watch [00:00 - 02:30] part of the video.
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).
Sum of all the elements of each subset should be equal.
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 special cases (Thankfully! already handled in the code):
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 print -1.
If (k = 1); Ways of partitioning in this case is one.
If (sum % k != 0); Ways of partitioning the sets with equal sum in this
case is 0.
For more clarity; watch this part of the video lecture
Let's try to draw the recursion tree for n = 3 and k = 2 before moving
to the code, keeping the above points into consideration:
At level-1, we have two sets and both 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 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 all 3 elements of the array in previous levels.
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.
Next answer does not violate any rule and the sum of each subset is equal to
(i.e. 3) therefore this is a valid answer.
Next two answers are also invalid as the sum of subsets varies in both cases.
Signature of the function:
public static void solution (int[] arr, int vidx,int n , int k,int[] subsetSum,int ssssf, ArrayList< ArrayList< Integer>> ans)
arr[]: input array of length n.
vidx: virtual index for operating array in recursion stack.
K: total levels.
ssssf: count of relevant sets so far. It stores the count of sets that have been
filled so far (non empty).
subsetSum[]: stores the sum of k different subsets corresponding to each
index.
ans: ArrayList of size k that stores the answer till that level.
Initially vidx is 0, ssssf 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 arr[vidx] to that set (make a new set) and add this value in the current value at jth index of subsetSum array and finally 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 ssssf in this case.
If the size of the jth set is not zero, we add arr[vidx] to that set and add this value in the current value at jth index of subsetSum array. (Case2). As the number of sets remains constant, we would not increase ssssf.
In pre-order we add the arr[vidx] to the jth set and also add this value in the current value at jth index of subsetSum array and in post-order we remove it and subtract this value in the current value at jth index of subsetSum array.
For the base case we check if vidx equals n, if it does then it means we have placed all the elements of the array in some subset. Then we will check if ssssf is equal to the k, this condition filters out the answers with an empty set.
Then we check if the sum of each subset is equal or not by capturing the subsetSum at 0 index, and initializing a Boolean flag to true and finally applying a for loop on the rest of the subsetSum array to check whether same value is present at each index or not.
If any value is different then we set the value of flag to false and we come out of the loop using break keyword.
After coming out of the for loop, we check if the value of flag is true or false. If it's true then we will print the answer in the required format and finally return.
For better understanding of the code, watch [11:08 - 19:31] part of the video.
Complete Code:
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[] arr = new int[n];
int sum = 0;
for(int i = 0 ; i < arr.length; i++) {
arr[i] = scn.nextInt();
sum += arr[i];
}
int k = scn.nextInt();
// if k is equal to 1, then whole array is your answer
if(k == 0) {
System.out.print("[");
for(int i = 0 ; i < arr.length; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println("]");
return;
}
//if there are more subsets than no. of elements in array or sum of all elements is not divisible by k
if(k > n || sum % k != 0) {
System.out.println("-1");
return;
}
int[] subsetSum = new int[k];
ArrayList< ArrayList< Integer > > ans = new ArrayList<>();
for(int i = 0; i < k; i++) {
ans.add(new ArrayList<>());
}
solution(arr,0,n,k,subsetSum,0,ans);
}
public static void solution(int[] arr, int vidx,int n , int k,int[] subsetSum,int ssssf, ArrayList> ans) {
if(vidx == arr.length) {
if(ssssf == k) {
int isum = subsetSum[0];
boolean flag = true;
for(int i = 1 ;i < subsetSum.length; i++) {
if(subsetSum[i] == isum) {
continue;
}else {
flag = false;
break;
}
}
if(flag == true) {
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(arr[vidx]);
subsetSum[j] += arr[vidx];
solution(arr,vidx + 1,n,k,subsetSum,ssssf + 1,ans);
ans.get(j).remove(ans.get(j).size() - 1);
subsetSum[j] -= arr[vidx];
break;
}else {
ans.get(j).add(arr[vidx]);
subsetSum[j] += arr[vidx];
solution(arr,vidx + 1,n,k,subsetSum,ssssf,ans);
ans.get(j).remove(ans.get(j).size() - 1);
subsetSum[j] -= arr[vidx];
}
}
}
}
java;
true";
Complexities:
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.
All the best for an exciting future!
Happy Coding!
