Как разбить числа от 1 до n на три множества так, чтобы сумма чисел в каждом была одинаковой?

@buster 

Существует несколько подходов к разбиению чисел от 1 до n на три множества с одинаковой суммой чисел. Один из подходов основан на использовании динамического программирования. Вот алгоритм на основе этого подхода:

1. Вычислите сумму всех чисел от 1 до n и назовите ее total_sum.
2. Если total_sum не делится нацело на 3, значит, невозможно разделить числа на три множества с одинаковой суммой. В таком случае верните пустые множества.
3. Создайте матрицу dp размером (n+1) × (total_sum/3 + 1), заполненную значениями False. Здесь dp[i][j] будет означать, можно ли получить сумму j, используя первые i чисел.
4. Установите значения dp[0][0] = True, так как можно получить сумму 0 без использования чисел.
5. В цикле от 1 до n: a) Вложенным циклом обратным ходом от total_sum/3 до 1: Если dp[i-1][j] = True, установите dp[i][j] = True, так как сумму j можно получить без использования числа i. Если dp[i-1][j-A[i]] = True, установите dp[i][j] = True, так как сумму j можно получить для i числа, добавив к сумме в j сумму числа i.
6. Если dp[n][total_sum/3] = False, значит, невозможно разделить числа на три множества с одинаковой суммой. В таком случае верните пустые множества.
7. Иначе, начиная с dp[n][total_sum/3], восстановите числа, используя dp массив. Поместите число n в третье множество и уменьшите total_sum/3 на значение числа n.
8. Для i от n-1 до 1: a) Если dp[i][total_sum/3] = True, поместите число i в третье множество и уменьшите total_sum/3 на значение числа i. b) Иначе, если dp[i][total_sum/3 + A[i]] = True, поместите число i во второе множество и увеличьте total_sum/3 на значение числа i. c) В противном случае, поместите число i в первое множество.
9. Верните три множества.

Приведенный алгоритм имеет временную сложность O(n * total_sum/3) и требует O(n * total_sum/3) дополнительной памяти для хранения dp матрицы.