Recursive-backtracking algorithm for solving the partitioning problem

Hey, i'm looking for some help to find an algorithm which divides an array of positive numbers into k-parts so that each part has the (approximately) the same sum ... let's say we have

1,2,3,4,5,6,7,8,9 en k=3 thn the algorithm should partition it like this 1,2,3,4,5|6,7|8,9 the order of the elements cannot be changed ... Finding a greedy algorithm is easy but i'm looking for a backtracking version which always returns the optimal solution ...

Annyone got any hints ?

Here is a solution that doesn't use any dynamic data structures such as lists. They are totally unnecessary and would in practice make the algorithm much slower than necessary.

Let K be the number of partitions here and N be the number of elements in your array.

int start[K];

void register() {
   /* calculate the error between minimum and maximum value partitions */
   /* partition boundaries are start[0], start[1], start[2], ... */
   /* if lower error than previously stored, remember the best solution */
}

void rec(int s, int k) {
  if (k == K) register();
  for (int i = s; i < N; i++) {
    start[k] = i;
    rec(i + 1, k + 1);
  }
}

/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */

Note: this is an O(n^K) algorithm. It is sub-exponential because this is not equivalent to the general NP-complete partitioning problem has here you are looking for contiguous segments of a linear array instead of arbitrary subsets of a given total set.