Partitioning an array into 3 sets

Question

Given an array of integers , Partition the array into 3 sets such that sum of the elements of the 3 sets are as close as possible.

My method is as follows:

1. Sort the array in the decreasing order
2. Insert the element into that set whose sum is minimum.

sort(a, a+n);
int o = 0, tw = 0, th = 0;

while(n--)
{
  if (o <= tw && o <= th)
    o += a[n];
  else if (tw <= o && tw <= th)
    tw += a[n];
  else 
    th += a[n];
}

Can anyone tell me What is wrong with my solution ? Or can advice a better Solution

Answer 1

here is brute-force java solution you can use, note - complexity of this solution is O(3^N), which is very very slow

/**
 * Returns absolute difference between 3 values in array
 */
static int getdiff(final int s[])
{
    return Math.abs(s[0] - s[1]) + Math.abs(s[1] - s[2]) + Math.abs(s[2] - s[0]);
}

/**
 * Calculates all possible sums and returns one where difference is minimal
 */
static int[] getsums(final int a[], final int idx, final int[] s)
{
    // no elements can be added to array, return original
    if (idx >= a.length)
        return s;

    // calculate 3 different outcomes
    final int[] s1 = getsums(a, idx + 1, new int[] {s[0] + a[idx], s[1], s[2]});
    final int[] s2 = getsums(a, idx + 1, new int[] {s[0], s[1] + a[idx], s[2]});
    final int[] s3 = getsums(a, idx + 1, new int[] {s[0], s[1], s[2] + a[idx]});

    // calculate difference
    final int d1 = getdiff(s1);
    final int d2 = getdiff(s2);
    final int d3 = getdiff(s3);

    if ((d1 <= d2) && (d1 <= d3))
        return s1;
    else if ((d2 <= d1) && (d2 <= d3))
        return s2;
    else
        return s3;
}

static int[] getsums(final int a[])
{
    return getsums(a, 0, new int[] {0, 0, 0});
}

static void printa(final int a[])
{
    System.out.print("[");
    for (final int t : a)
        System.out.print(t + ",");
    System.out.println("]");
}

static public void main(final String[] args)
{
    final int a[] = new int[] {23, 6, 57, 35, 33, 15, 26, 12, 9, 61, 42, 27};

    final int[] c = getsums(a);

    printa(a);
    printa(c);
}

sample output:

[23,6,57,35,33,15,26,12,9,61,42,27,]
[115,116,115,]