Как разбить массив на подмассивы с одинаковой суммой числ?

Question

[merifry]

У меня есть масив с числами от 1 до 8, например. [1,2,3,4,5,6,7,8]
И его надо разбить на несколько частей, в даном примере 2, чтобы получилось так, что и в одном и в другом сумма одинаковая. Например:
[1,4,6,7]
[2,3,8,5]
Как такое сделать?

есть пока такое, где s-сумма которая должна быть, n - это число, а k - на сколько разделить

n, k = map(int,input().split())
m1=[]
m2=[]
s=((n+1)/2*n)/k  
for i in range(1, n+1):
    print(i)
print(s)

Comments

[Алан Гибизов]

А как пробовали и что не получилось?

[Модератор]

За готовыми рецептами надо обращаться на фриланс. Сюда надо приносить свою попытку решения, показать что ожидалось и что получилось. Тогда, возможно, помогут.
В данном виде это не вопрос, а задание, и может быть удален за нарушение п.5.12 Регламента.

[merifry]

Алан Гибизов, уже отредактировал, это все что есть, а как именно разделить не знаю

[Roman K]

У задачи мало ограничений. Например, какой максимальный размер пула? Есть ли там повторения? Должны ли быть использованы все числа из пула? Должны ли "части" быть равными по количеству элементов? Нужно ли учитывать (иными словами, может ли быть), что отдельный элемент пула может быть больше суммы?

[merifry]

Roman Kitaev, максимальный размер это n/k символов, повторений нет, использовать все числа, должны быть равными по количеству и по сумме чисел

[Алан Гибизов]

merifry, задача делится на две части: алгоритм, т.е. как решать, и код, воплощающий алгоритм. У вас проблема с кодом или с алгоритмом? Можете алгоритм словами описать? Если проблема с алгоритмом, то надо писать в тэг «алгоритмы», а не «питон».

Answer 1

[Roman K]

Ну тогда примерно так. Приправить, добавить thread-safety, избавиться от рекурсии и дичайшего выделения памяти по своему вкусу:

def solve(buckets: list[frozenset[int]], pool: frozenset[int], sum_: int, solved: set[frozenset[frozenset[int]]], tried: set[frozenset[frozenset[int]]]):
    assert all(x <= sum_ for x in pool)

    tried.add(frozenset(buckets))
    if not pool and set(sum(bucket) for bucket in buckets) == {sum_} and len(set(len(b) for b in buckets)) == 1:
        solved.add(frozenset(buckets))

    for x in pool:
        for i, bucket in enumerate(buckets):
            new_buckets = buckets[:]
            new_buckets[i] = bucket | {x}
            if frozenset(new_buckets) not in tried:
                solve(new_buckets, pool - {x}, sum_, solved, tried)

    return solved


if __name__ == '__main__':
    for solution in solve([frozenset(), frozenset()], frozenset([1,2,3,4,5,6,7,8]), 18, set(), set()):
        print(solution)

А ещё это полный перебор. Жадные, щедрые и другие решения ищите где-нибудь здесь