Problem
Partition to K Equal Sum Subsets
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:
1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.
Solution
Prove an array is able to divide to K equal sum subsets won't be easy at first sight, so let's first rule out those cases that can not be divided.
- sum%k != 0
- the largest element is larger than sum/k
Elements equal to target can be put into one array by itself, elements equal 0 can be put anywhere.
For the elements left, unfortunately, we need to enumerate all the possible cases until we found the solution. Assuming there are n elements left. How many combinations we need to try?
This is equivalent to a statistics problem: how many possible ways of putting n balls into k buckets, each bucket must have at least one ball.
For the statistics problem, we first first pick n-k balls, randomly put them into k buckets. Each ball has k choices, the total choice is k^(n-k). After that, there are only k balls left, there are k! ways of put k balls into k bucket. So that set high boundary for our time complexity O(k^(n-k)*k!).
There are several ways of solving the above statistics problem.
Approach one could be. We enumerate all the subsets excluding the self array and empty array. The cost will be 2^N. Then we filter out all those with sum equal to target. Then we randomly pick k of them, test if their elements add up to the original array.
Approach two could be. We pick one element i at a time from the n elements, try to put into one of the bucket m from m = 0 to k-1. If success, we pick another element ++i, try to put into one of bucket m from m = 0 to k-1. If fail, we remove the element i from bucket m, return false. Recursively doing this will iterate through all the possible scenarios. The exit condition is we have tried the last element in i in the array.
Let's code according to approach two.
public class KEqualSum {
public static boolean canDo(int[] a, int k) {
Arrays.sort(a);
int sum = Arrays.stream(a).sum();
if(sum%k!=0) return false;
if(sum == 0 && a.length >= k) return true;
int target = sum/k;
int i = a.length-1;
int j = 0;
if(a[i] > target) return false;
while(i >= 0 && a[i] == target) {
i--;
k--;
}
while(j <= i && a[i] == 0) {
j++;
}
int[] sums = new int[k];
return canDivide(a, sums, i, j, target);
}
private static boolean canDivide(int[] a, int[] sums, int curIndex, int stopIndex, int target) {
if(curIndex < stopIndex) return true;
for(int i = 0; i < sums.length; i++) {
if(sums[i] + a[curIndex] <= target) {
sums[i] += a[curIndex];
if(canDivide(a, sums, --curIndex, stopIndex, target)) return true;
sums[i] = a[curIndex];
}
}
return false;
}
public static void main(String...args) {
int[] a = {4, 3, 2, 3, 5, 2, 1, 0, 0, 0, 0};
int k = 4;
System.out.println(canDo(a, k));
}
}
Time cost O(k^(n-k)*k!), space cost O(N).
