Last Updated: 16 Dec, 2020

K subsets with equal sum

Easy

Asked in companies

Solve now

Problem statement

You are given an array of integers "ARR" of length 'N' and an integer 'K'. Your task is to find whether or not you can divide the array "ARR" into 'K' subsets with equal sum.

A subset of an array "ARR" is another array whose every element is present in array "ARR".

For example:

If ARR = {1, 2, 3, 4}, then array {3,4} is a subset of "ARR" because both 3 and 4 are also elements of "ARR".

For example:

Consider array ARR = {3, 5, 2, 4, 4} and K = 2, i.e. you have to divide "ARR" into 2 subsets with equal sum. The division will be {4, 5} and {2, 3, 4} with sum 9.

Note:

Every element of the array must occupy only one subset.

Input Format:

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains two space-separated integers ‘N’ representing the size of the array and ‘K’.

The second line contains N space-separated integers that represent elements of the array ARR.

Output Format

For each test case, return true if it is possible to divide "ARR" into 'K' subsets of equal sum, false otherwise.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <=1000
1 <= K <= 20
1 <= ARR[i] <= 1000

Time limit: 1 second

Solve now

Approaches

01 Approach

Consider function “SPLITARRAY” that accepts array “ARR” and ‘K’ and do

Check if K=1, that means you do not have to divide array. And the entire array will be the answer, so we return TRUE.
Check if N < K, that means we have to divide ‘N’ elements into ‘K’ subsets, which is not possible, so we return FALSE.
We define a variable "SUM" as the sum of all elements of "ARR".
Check if “SUM % K” is zero. If it is not zero that means we can not divide the array into 'K' parts with equal sum(integral), so we return FALSE.
Define variable "SUBSET" to store the value of sum for equal subsets, i.e. assign "SUM / K" to “SUBSET”. This is the value of sum all subsets must-have.
Let us define two arrays:
- "SUMOFSUBSETS": Integer array of size ‘K’ to store sum for ‘K’ subsets.
- “ISCONSIDERED”: Boolean array of size ‘N’ to mark which elements are already considered for any of the subsets.
Iterate over SUMOFSUBSETS[i] for each 1<= i <=K and initialize it to 0.
Iterate over ISCONSIDERED[i] for each 1<= i <=N and initialize it to FALSE.
Call utility function "SPLITARRAYUTIL" for "ARR", K, N, "SUMOFSUBSETS", “ISCONSIDERED”, “SUBSET”, 0(START INDEX), “N - 1” (INDEX UPPER LIMIT) and store the value into “RESULT”.
Return "RESULT".

Now, the utility function “SPLITARRAYUTIL” which we used earlier basically picks all the elements of “ARR" one by one and places them in available subsets until the max sum limit of the array is reached. It accepts integer array "ARR", the value 'K', size of array ‘N’, integer array “SUMOFSUBSETS”, boolean array “ISCONSIDERED”, the max limit of sum for a subset "SUBSET", the current index for subset “CURRINDEX” and upper index limit “MAXLIMIT” as parameters and does:

If SUMOFSUBSETS[CURRINDEX] is equal to “SUBSET”, we do:
1. Check if "CURRINDEX" is “K - 2”, that means we have already made "K - 1" subsets with the equal sum, now the remaining elements will automatically form Kth subset, hence we return TRUE.
2. Else call “SPLITARRAYUTIL” for “ARR”, ‘K’, ‘N’, “SUMOFSUBSETS”, "ISCONSIDERED", "SUBSET", “CURRINDEX + 1”, "N - 1" and store value in “RESULT”.
3. Return "RESULT".
Iterate for each MAXLIMIT >= i >= 0 and do:
1. Check if the current element is already considered in any of the subsets, if yes, skip the remaining part of the loop.
2. Define an integer “TEMP”, and store SUMOFSUBSETS[CURRINDEX] + ARR[i]. This variable represents the value of sum that we’ll get if we add ARR[i] to that subset.
3. If “TEMP” is less than or equals to “SUBSET”, we do:
  1. We make, ISCONSIDERED[CURRINDEX] = TRUE.
  2. Add ARR[i] to SUMOFSUBSET[CURRINDEX].
  3. Call SPLITARRAYUTIL for “ARR”, ‘K’, ‘N’, “SUMOFSUBSETS”, "ISCONSIDERED", "SUBSET", "CURRINDEX", “i - 1” and store value in variable "NEXT".
  4. We assign ISCONSIDERED[CURRINDEX] = FALSE and subtract ARR[i] from SUMOFSUBSET[CURRINDEX].
  5. If "NEXT" is true we return TRUE.
We return FALSE.

Solve now