recursion - Recursive-backtracking algorithm for solving the partitioning problem -

hey, i'm looking find algorithm divides array of positive numbers k-parts each part has (approximately) same sum ... let's have

1,2,3,4,5,6,7,8,9 en k=3 thn algorithm should partition 1,2,3,4,5|6,7|8,9 order of elements cannot changed ... finding greedy algorithm easy i'm looking backtracking version returns optimal solution ...

annyone got hints ?

here solution doesn't use dynamic data structures such lists. totally unnecessary , in practice make algorithm slower necessary.

let k number of partitions here , n number of elements in array.

int start[k];  void register() {    /* calculate error between minimum , maximum value partitions */    /* partition boundaries start[0], start[1], start[2], ... */    /* if lower error stored, remember best solution */ }  void rec(int s, int k) {   if (k == k) register();   (int = s; < n; i++) {     start[k] = i;     rec(i + 1, k + 1);   } }  /* entry */ start[0] = 0; rec(1, 1); /* output best solution found @ register() */ 

note: o(n^k) algorithm. sub-exponential because not equivalent general np-complete partitioning problem has here looking contiguous segments of linear array instead of arbitrary subsets of given total set.