K subsets with equal sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
32 upvotes
Asked in companies
BarclaysNagarro Software

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

3 
5 2
3 5 2 4 4
9 6 
1 9 6 8 6 9 9 9 9
7 4
4 4 4 1 1 1 1

Sample Output 1:

TRUE
FALSE
TRUE

Explanation For Sample Input 1:

For first case, 
Array can be divided into 2 subsets as {2, 3, 4} and {4, 5} with sum 9.

For the second case,
Array can not be divided into 6 subsets with equal sum.

For the third case, 
Array can be divided into 4 subsets as {4}, {4}, {4} and {1, 1, 1, 1} with sum 4.

Sample Input 2:

5
10 5
1 2 3 4 5 6 7 8 9 10
7 7
7 7 7 7 7 7 7
7 3
1 2 3 4 5 6 7
5 2
3 5 7 11 13
3 5
1 2 3

Sample Output 2:

TRUE
TRUE
FALSE
FALSE
FALSE
Hint

Try to find what is the maximum sum value you can use to make a subset, then make each subset one by one.

Approaches (1)
Recursive

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:

  1. 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".
  2. 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.
  3. We return FALSE.
Time Complexity

O(K ^ (N - K) * K!) where ‘N’ is the length of the array and ‘K’ is the number of subsets.

 

We try each combination of divisions that costs K ^ (N - K) operations, and since the number of ways to order the subsets is K!, the overall complexity is O(K ^ (N - K) * K!).

Space Complexity

O(K ^ (N - K) * K!) where ‘N’ is the length of the array and ‘K’ is the number of subsets.

 

We try each combination of divisions that costs K ^ (N - K) recursive calls, and since the number of ways to order the subsets is K!, the overall recursive depth is O(K ^ (N - K) * K!).

Code Solution
(100% EXP penalty)
K subsets with equal sum
Full screen
Console