Итак, я пытаюсь придумать алгоритм для программы, которая будет использовать рекурсию для получения массива целых чисел x и разделения его на n наборов. Эти числа могут быть как положительными, так и отрицательными. Наборы должны иметь наименьшую возможную разницу между ними.
Например, если вы дали программе массив int [1, 2, 3, 4] и сказали ей разделить на 3 группы, то она разделила бы его на [1, 3] [2] и [4], где разница между наборы равны 2. Другой пример: если вы дали массив [6, 6, 6, 10, 10] и сказали ему разделить на 2 группы, тогда он разделит его на [10, 10] и [6, 6, 6], где разница между множествами равна 2.
Мы можем предположить, что массив отсортирован в порядке возрастания (с наименьшим слева и наибольшим справа), поскольку сортировка будет простым оператором сортировки. Любые идеи?
РЕДАКТИРОВАТЬ: я понимаю, что имею дело с проблемой разделения, и я пробовал жадный алгоритм, в котором вы переходите от наибольших чисел к наименьшим и помещаете их в группу с наименьшей суммой, но это не сработает для второго примера, который я привел выше поэтому я ищу более надежный алгоритм.