Split the given array into K subsets such that maximum sum of all subsets is minimum

Question

Given an array of $N$ elements, $A$, and a number $K$. (1ドル \leq K \leq N$) .
Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum subset sum achievable out of $K$ partitions formed, must be the minimum possible.
Find that possible subset sum.

For example $A = [11, 11, 5, 10, 5]$ and $K = 2$ the partitioning that satisfies the problem will be $\{\{11, 5, 5\}, \{11, 10\}\}$ so that the defined maximum sum will be 21ドル$ and it is the minimum of all different K-Partitionings of $A$.

---

The question came up to my mind when I was solving a similar problem for only K contiguous subarrays which could be easily solved using a binary search over all possible maximum sums of the array($O(\log{\text{SUM}})$).

For example for the same $A$ defined in above maximum sum is at least the maximum number which is 11ドル$ and is at most the total sum of all elements which is 42ドル$.

Then in each step of binary search we check whether it is possible to split $A$ into at most $K$ contiguous subarrays or not so that the maximum sum over all subarrays will be at most the mid point of binary search step(needs one loop over $A$ then $O(n)$). If yes we recurse on the left side, otherwise we recurse on the right side.
in overall the algorithm will have a $O(n\log{\text{SUM}})$ time complexity.
But I can't find a way to generalize the checking process in every step of the binary search so that it checks whether for a specific maximum sum like $s^{*}$ is it possible to partition $A$ with at most $K$ subsets so that the maximum sum over all subsets will be at most $s^{*}$ with a good time complexity.

I should also mention that the above motivation is not necessarily the only way accepted to solve this problem and every other idea will be appreciated.

• Yuval Filmus: Your problem is NP-hard by reduction from PARTITION.
• Ashkan Khademian: So is there any NP solution for it? for example somehow using backtrack? @YuvalFilmus.
• Yuval Filmus: The NP solution is to try all possible splits.

Answer 1

Use backtracking to check all the possible combinations and using a heuristic function you can reduce the search space to reach answer quickly. I've used one such solution to distribute the load as an array of n elements evenly across k partitions. Let me know if you need the code as well.