Максимальная комбинация для данного списка ⇐ Python

[Anonymous]

Мне нужен помощник для реализации следующего вопроса на Python;
Есть заданный список:

Код: Выделить всё

nums = [1, 1, 4, 2, 3, 3, 2, 5]

Требуется написать код Python, который получает максимальное количество групп комбинаций с суммой 6.
порядок не имеет значения; [1, 4] и [4, 1] считают одной и той же комбинацией. ограничения: Числа в списке являются натуральными числами; положительные целые числа (не десятичные и не дробные), которые больше 0. Длина списка не указана.

Код: Выделить всё

[[1, 5], [2, 4], [3, 3]] and [[1, 2, 3], [1, 5], [2, 4]]

— это группы с максимальной комбинацией (=3).
Если число использовалось в одной подгруппе в группе комбинаций, его нельзя использовать повторно.
например число "4", если оно используется в [1, 1, 4], его нельзя использовать повторно в другой комбинации [4, 2] в той же группе(если оно не появляется дважды в список ввода).
Если возможно, был бы рад узнать, как ее решить, чтобы получить сами комбинации (в том числе и до максимального количества).
Я' Я что-то написал, но это крайне неэффективно с точки зрения временной сложности.

Код: Выделить всё

from collections import Counter

def get_combination_groups(array: list, total_size: int) -> list:
out = []
array.sort()

def dfs(arr, total, cur):
if total == 0:
out.append(cur.copy())
return
if total < 0 or len(arr) == 0:
return
prev = -1
for i in range(len(arr)):
n = arr[i]
if prev == n:
continue
reminder = total - n
cur.append(n)
dfs(arr[i + 1:], reminder, cur)
prev = n
cur.pop()
dfs(array, total_size, [])
return out

def is_valid(remain: dict, count_b: dict) -> bool:
for key in count_b:
if not remain.get(key) >= count_b[key]:
return False
return True

def filter_result(result: list, arr: list) -> list:
output = []
start_count = Counter(arr)
for i in range(len(result)):
remain = start_count.copy()
i_count = Counter(result[i])
remain.subtract(i_count)
out_tmp = [result[i]]
for j in range(i + 1, len(result)):
j_count = Counter(result[j])
if is_valid(remain, j_count):
out_tmp.extend([result[j]])
remain.subtract(j_count)
output.append(out_tmp)
return output

nums = [1, 1, 4, 2, 3, 3, 2, 5]
total_sum = 6
res = get_combination_groups(nums, total_sum)
print(filter_result(res, nums))`

Вывод кода:
[[[1, 1, 2, 2], [3, 3]], [[1, 1, 4], [3, 3]], [[1, 2, 3], [1, 5], [2, 4]], [[1, 5], [2, 4], [3, 3]], [[2, 4], [3, 3]], [[3, 3]]]

Подробнее здесь: https://stackoverflow.com/questions/793 ... given-list