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

[Anonymous]

Мне нужен помощник, который сможет реализовать на Python следующий вопрос;
Есть такой список:nums = [1, 1, 4, 2, 3, 3, 2, 5]
Требуется написать код Python, который получает максимальное количество групп с суммой 6.
Вот возможные комбинации:
[[[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]]]
Максимальное количество комбинаций — 3.
Если число использовалось в группе комбинаций, его нельзя использовать повторно.
Например. число «4», если оно используется в [1, 1, 4], его нельзя использовать снова в другой комбинации [4, 2] (если оно не появляется дважды в списке ввода).
Если возможно, был бы рад узнать, как ее решить, чтобы получить сами комбинации (в том числе и до максимального количества).
Я что-то писал, но крайне неэффективно с точки зрения временной сложности.
def get_combination_groups(array: list, total_size: int) -> list:
out = []
array.sort()

def dfs(arr, total, cur, have):
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
if prev == n:
continue
reminder = total - n
cur.append(n)
dfs(arr[i + 1:], reminder, cur, have)
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)
remain.subtract(i_count)
out_tmp = [result]
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))`


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