Algorithm for finding the sum of array members close to the average value?

Question

Algorithms

It is necessary to find the most optimal option for dividing the array, i.e. such that the sum of the members of the largest group would be the minimum of all possible options.

Example:
Given an array: [1, 3, 7, 4, 2, 5, 8, 6, 9];
number of groups: 3;
options for dividing an array into groups: [17, 19, 9], [17, 13, 15], [15, 21, 9], [15, 15, 15], [11, 19, 15], [11, 11 , 23];
the largest sums of numbers in each of the arrays: 19, 17, 21, 15, 19, 23;
desired variant: [15, 15, 15], because 15 < 17 < 19 < 21 < 23.

There is such a solution, is a normal enumeration, and its capabilities are limited by the depth of recursion, it is not suitable for large arrays and groups. Maybe someone faced a similar problem and knows a more efficient solution. The algorithm can be used to find the height of a flex container in case of dynamic loading of blocks of different heights: example .

Answer 1

Theoretically:
1. Sort the array from smallest to largest;
2. Find the sum of all members of the array;
3. Find the average by dividing the sum of all members by the number of groups (round to the nearest integer);
4. Add the members of the sorted array until a number close to the average is typed. As soon as the required number has been accumulated, we go further along the array until we collect the sum in the next group

Answer 2

There is no simple solution to this problem.
One option is overkill, as you have already stated. You can do all sorts of heuristics-cutting, such as trying to combine the larger element first with the remaining two smaller ones.
All sorts of annealing simulation methods or genetic algorithms can still work.
You can also try to reduce the problem to integer linear programming and run it through one of the existing solvers.