Erkennen von Zahlenpaaren

[ibp]

Zitat von Dejan Vu:

Korrigiert mich bitte, aber wenn es hier um Teilmengen (nicht Partitionen) geht, dann ist das doch popelig.

Also: Gegeben zwei Mengen A und B. Gesucht ist die Menge aller Teilmengen T, sodass für jedes t aus T gilt: Es existiert ein Element b aus B mit b=Summe der Elemente aus t.

Beispiel: A = (1,2,3,4). B=(5,7,10)
Teilmengen =
(1),(2),(3),(4),
(1,2),(1,3),(1,4),
(2,3),(2,4),(3,4),
(1,2,3),(1,2,4),(2,3,4),
(1,2,3,4)
Die Teilmengen 't', deren Summe entweder 5,7 oder 10 ist, sind fett markiert.

Ich muss also nur alle Teilmengen aus A bilden, summieren und schauen, ob der Wert in B vorkommt. Ganz einfach. Dauert nur. Denn es gibt 2^n Teilmengen einer n-elementigen Menge.

Wenn Sort(A) dann kann man ggf. mit Min(B), Max(B) das ganze noch einschränken und optimieren, besser für kleine Max(B)-Min(B).