Разделить массив на пары различной глубины

Пусть есть массив a[0],a[1],..,a[6], Я хочу реализовать алгоритм, который будет возвращать всевозможные глубины. Чтобы сделать его более понятным, рассмотрим, что я должен вернуть алгоритм для разных значений глубины

depth: 1,
return:
(a[6] - a[0]); /*the only possible case for depth = 1*/

depth: 2,
return:
(a[1] - a[0]) + (a[6] - a[2]); /*first case*/
(a[2] - a[0]) + (a[6] - a[3]); /*second case*/
(a[3] - a[0]) + (a[6] - a[4]); /*third case*/
(a[4] - a[0]) + (a[6] - a[5]); /*fourth*/

depth: 3,
return:
(a[1] - a[0]) + (a[3] - a[2]) + (a[6] - a[4]); /*first case*/
(a[1] - a[0]) + (a[4] - a[2]) + (a[6] - a[5]); /*second case*/
(a[2] - a[0]) + (a[4] - a[3]) + (a[6] - a[5]); /*third case*/

Это был пример для массива длины 7, Я хочу, чтобы алгоритм работал для массива произвольной длины.

Я смог реализовать алгоритм с помощью рекурсии. Ниже приведен код на C ++

int arr[101]; /*Original array with length N = 100*/
set <__int64> Partitions; /*Set, for accumulation of the sum of the partitions*/

void get_partitions(int start, int end, int depth, int sum) {
if (depth == 1) {
sum += (arr[end] - arr[start]);

Partitions.insert(sum);
}
else {
int k = end - 2 * (depth - 1);
int new_start = start + 1;

while (new_start <= k) {
int current_sum = (arr[new_start] - arr[new_start - 1]);

get_partitions((new_start + 1), end, (depth - 1), (sum + current_sum));

new_start++;
}
}
}

int main() {
get_partitions(0, 100, 5, 0);

//processing of Partitions

return 0;
}

У этой реализации есть проблема работы. Для массива большого размера время выполнения программы слишком велико.

Можно ли улучшить алгоритм? Есть ли другие реализации этого алгоритма? Буду благодарен за ответы.