Mhm, auf den ersten Blick sah es nach
Partition aus, allerdings scheinst du ja eine passende Partition zu haben.
EDIT: JasonDX hat recht; das Partitionsproblem sollte sich darauf reduzieren lassen. Eingabe von Partition wird M1, M2 hat zwei Elemente: jeweils die Hälfte der Summe aller Elemente in M1.
Ich verstehe das Problem so: finde für jedes Element aus Menge2 eine Summe aus Elementen aus Menge1, sodass kein Element aus Menge1 doppelt verwendet wird (?)
Klar ist, dass dann immer alle Elemente von Menge1 benutzt werden müssen, da die Summe der Elemente gleich ist. Was heißt also ein "kurzes Ergebnis"?
Es gibt nicht immer ein Ergebnis. Beispiel:
M1 = 2, 4, 6
M2 = 3, 9
Es kann unterschiedliche Ergebnisse geben (welches ist hier besser/kürzer?):
M1 = 1, 2, 2, 3
M2 = 5, 3
5 = 1 + 2 + 2 und 3 = 3
5 = 2 + 3 und 3 = 2 + 1