How to divide an array into 3 parts with the sum of each part roughly equal

Question

I have an arranged array and I want to divide it into 3 parts so that their sum are closest to each other.

Ex: I have this array:

    10, 8, 8, 7, 6, 6, 6, 5

so it'll be divided into 3 part like:

    p1 {10,8} sum = 18
    p2 {8,7,6} sum = 21
    p3 {6,6,5} sum = 17

Answer 1

The original poster already has a working solution (noted in comments) to split the array into two parts with equal sums; call this split2. The three-part version can be constructed using split2.

1. Add to the array a new number equal to one-third of the sum of the original numbers.
2. Split the array into two parts using split2.
3. One part has the number that was added; remove it.
4. Split the other part into two using split2.

Answer 2

This is like two-Partition problem which is NP-Hard but not in strong sense, you can have an O(nK) algorithm for it where K is size of your input sum, See pseudo polynomial time algorithm for subset sum, Also See my answer for divide-list-in-two-parts-that-their-sum-closest-to-each-other, but in your case you should just add another dimension to process it.

Answer 3

// calculate total
total = 0;
for(i = 0; i != size; ++i) {
   total += array[i];
}

// partition
n_partitions = 3;
current_partition = 1;
subtotal = array[0];
for(i = 1; i != size; ++i) {
   if(subtotal + array[i] > total / n_partitions) {
      // start new partition;
      current_partition++;
      subtotal = array[i];
   } else {
      // push to current partition
      subtotal += array[i];
   }
}

Answer 4

Try the following code

int total = 0, partSum = 0, partIndex = 0;
int noOfParts = 3; //Initialize the no. of parts
int[] input = { 10, 8, 8, 7, 6, 6, 6, 5 };
int[] result = new int[noOfParts]; //Initialize result array with no. of locations equal to no. of parts, to store partSums
foreach (int i in input) //Calculate the total of input array values
{
    total += i;
}
int threshold = (total / noOfParts) - (total / input.Length) / 2; //Calculate a minimum threshold value for partSum
for (int j = input.Length - 1; j > -1; j--)
{
    partSum += input[j]; //Add array values to partSum incrementally
    if (partSum >= threshold) //If partSum reaches the threshold value, add it to result[] and reset partSum  
    {
        result[partIndex] = partSum;
        partIndex += 1;
        partSum = 0;
        continue;
    }
}
if (partIndex < noOfParts) //If no. of parts in result[] is less than the no. of parts required, add the remaining partSum value
{
    result[partIndex] = partSum;
}
Array.Reverse(result);
foreach (int k in result)
{
    Console.WriteLine(k);
}
Console.Read();     

I've tested this with various values in array(arranged in descending order) and also with different value for no. of parts(3,4,5...) and got good results.