Maximale Kombination für eine bestimmte Liste ⇐ Python

[Guest]

Ich brauche einen Assistenten, der die folgende Frage in Python implementiert.
Es gibt eine vorgegebene Liste:

Code: Select all

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

Die Anforderung besteht darin, einen Python-Code zu schreiben, der die maximale Anzahl von Gruppen mit der Summe von 6 erhält.
Dies sind die möglichen Kombinationen:

Code: Select all

[[[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]]] 

Die maximale Anzahl an Kombinationen beträgt 3.
Wenn eine Zahl in einer Kombinationsgruppe verwendet wurde, kann sie nicht noch einmal verwendet werden.
z.B. Wenn die Zahl „4“ in [1, 1, 4] verwendet wird, kann sie nicht erneut in einer anderen Kombination [4, 2] verwendet werden (es sei denn, sie erscheint zweimal in der Eingabeliste).
Wenn möglich, würde ich gerne wissen, wie ich es lösen kann, um die Kombinationen selbst zu erhalten (auch bis zur maximalen Anzahl).
Ich habe etwas geschrieben, aber ist im Hinblick auf die zeitliche Komplexität äußerst ineffizient.

Code: Select all

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[i]
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[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))`