How to Partition an array into N smallest sum subsets?

Question

How to partition an integer array into N subsets such that the sum of these subsets is minimum?

For example the array is consisted of 11 elements and I need 6 subsets out of it.

{2,1,1,3,4,4,3,2,1,2,3}

The subsets : {2,1,1,3}, {4}, {4,3}, {3,2}, {1,2}, {3} Minimum sum=7.

an alternative answer: {2,1,1} {3,4} {4} {3,2} {1,2} {3} Minimum sum=7.

Note: The order in which the numbers appear in the original set, must be maintained while partitioning.

• Carlos: I don't understand what you mean by minimum sum. There's a set in that first line with sum 3.
• Arijit Pramanick: Dividing the array into N subsets, such that the sum of each subset is less than or equal to the minimum sum possible from each subset.
• Arijit Pramanick: Try making 6 partitions where the sum of each partition will be less than 7.
• tobias_k: The question does not make much sense. Do you want to minimize the maximum sum of the subsets? Also, I think you mean "list" not "set".
• interjay: I think you meant to say "Maximum sum=7" for your examples. And you want to find the minimum possible maximum sum.

Answer 1

One possible approach is to binary search for the answer.

We need a procedure that would check whether we can partition the set using only sums equal or below a parameter, S. Let's call this procedure onlySumsBelow(S).

We can use a greedy solution to implement onlySumsBelow(S). Always add as many elements as possible in each subset, and stop just before reaching a sum larger than S (I am assuming here that we don't have negative elements, which may complicate the discussion). If we cannot reach the end of the sequence using the allowed number of subsets, then the sum is not valid (it is too small).

function onlySumsBelow(S) {
 partitionsUsed = 1;
 currentSum = 0;
 for each value in sequence {
 if (value > S) return false;
 if (currentSum + value > S) {
 // start a new partition
 currentSum = value; 
 partitionsUsed++; 
 } else {
 currentSum += value;
 }
 }
 return partitionsUsed <= N;
}

Once we have the onlySumsBelow(S) procedure, we can binary search for the answer, starting with an interval that at the left end has a value that ensures that the searched answer is not below (e.g. 0) and at the right end has a large enough number that ensures that the searched answer is not above (e.g. the sum of all numbers in the sequence).

If the efficiency is not a concern, instead of binary searching you can simply try multiple candidate answers one by one, starting from a small enough value, e.g. sum of all numbers divided by N, and then increasing by one until reaching a fine solution.

Remark: without the note in the end of the question (that restricts us to taking into account subsets of numbers that appear at neighboring positions in the input) the problem is NP-complete, since it is a generalization of the Partition problem, which only uses two sets.

• Arijit Pramanick: how can I maintain the number of partitions while adding numbers through the procedure onlySumsBelow(S) ?
• danbanica: I added some pseudocode for the onlySumsBelow(S) procedure. Also, mentioned that if efficiency is not a concern you can avoid the binary search and use a linear search.