Partition to K Equal Sum Subsets

About the problem:

Given a vector of integers and an integer k, we are to find if we can divide the array into k non-empty subsets with equal sums. Return true if we can or otherwise, false.

Example 1:
Input: arr = [5,2,1,2,3,4,3], k = 4
Output: true
Explanation: Possible subsets are- [2,3],[2,3],[5],[1,4]

Example 2:
Input: arr = [5,2,1,2,3,4,1], k = 4
Output: false

Precomputation

Before discussing the approaches we should check if it is feasible for the array to be divided into k equal sets or not. For that, compute whether the sum of integers of the array is divisible by k. If not, we cannot divide the array and the size of the array must be equal or greater than k.

For the above input [5,2,1,2,3,4,3], k = 4. Here the length of the array, i.e., n >= k and the sum, i.e., 20 is divisible by 4, so 20%4==0.

Approach #1: Backtracking

1. Consider a sum of the current subset as currSum, we are at index i, and we want the sum of each subset equal to reqSum = sum(nums[])/k.

2. We will use a visited[] to keep hold of already used elements.

3. If currSum + nums[i] > reqSum, we can only skip the ith element and go to the next element.

4. If !visited[i] and currSum + nums[i] <= resSum, we have two choices, either to include it or not include it in the current subset.

5. If we include it, we will make visited[i] = true so that the current element cannot be added to any other subset again.

6. If we find that taking this choice gives us true, we will return true.

7. Otherwise, we will exclude nums[i] from currSum by making visited[i] = false and go to the next element.

8. If at any point we find currSum == reqSum, it means we found a subset with the required sum, so call backtrack for k-1 th subset from 0th index.

9. If your k == 0, it means we found k subsets whose sum is reqSum.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool backtrack(vector < int > & arr, int i, int reqSum, int currSum, vector < bool > & isVisited, int k) {
  if (k == 0)
    return true;
  if (reqSum == currSum)
    return backtrack(arr, 0, reqSum, 0, isVisited, k - 1);

  if (i == arr.size())
    return false;

  if (!isVisited[i] && arr[i] + currSum <= reqSum) {
    isVisited[i] = true;
    if (backtrack(arr, i + 1, reqSum, currSum + arr[i], isVisited, k))
      return true;
    isVisited[i] = false;
  }

  return backtrack(arr, i + 1, reqSum, currSum, isVisited, k);
}

bool canPartitionIntoKSubsets(vector < int > & arr, int k) {

  int sum = 0;
  for (int ele: arr) sum += ele;
  if (sum % k != 0) return false;

  int n = arr.size();

  vector < bool > vis(n, false);
  return backtrack(arr, 0, sum / k, 0, vis, k);
}

Time complexity: O(k*2^n), for every subset we traverse the whole array and make two recursive calls almost in each traversal.

Approach #2: Bit Masking

In this approach we check every subset for the sum = sum/k and if the subset has the req sum we increase the count. If the total count is greater than equal to k we return true. We use bit masking to check if each subset contains sum = totalSum/k. Since each element can be taken only once we use a variable, gone, to keep track of the elements chosen.
For example, if the gone variable binary representation is 10110 then we have chosen the second, third, and the fifth element.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool canPartitionIntoKSubsets(vector < int > & nums, int k) {

  int n = nums.size();
  int t = (1 << n);
  sort(nums.begin(), nums.end(), greater < int > ());

  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += nums[i];
  }

  if (sum % k != 0) {
    return false;
  }

  sum = sum / k;
  int cnt = 0;
  int gone = 0;

  for (int m = 0; m < t; m++) {
    int x = 0;
    if (!(m & gone)) {
      for (int i = 0; i < n; i++) {
        if (m & (1 << i)) {
          x += nums[i];

        }
      }
      if (x == sum) {
        gone = m;
        cnt++;
      }
    }
  }
  return cnt >= k;
}

Time complexity: O((2^n)*n)