Ganz einfach. Dauert nur. Denn es gibt 2^n Teilmengen einer n-elementigen Menge.
Und dir ist klar das 2^1000 eine nicht unbedingt kleine Zahl ist?
Meister, was meinst Du? Ob mir das klar ist?
Also ohne Backtracking wird es nicht gehen.
Delphi-Quellcode:
foreach (t in Teilmengen(MengeVonZahlen)) do
if DieAndereMenge.Enthaelt(t.Summe) then
Writeln(t.ToString);
Schon mal nicht 'Backtracking'. Bleibt noch 'Teilmengen' bzw. die dort enthaltene Funktion 'NächsteTeilmenge'. Die wird man eleganterweise rekursiv definieren, aber es geht auch iterativ, fällt mir nur gerade nicht ein.
Gibt es in Delphi eigentlich ein Äquivalent zu 'IEnumerable<T>' und etwas wie ein 'yield'?
...
Sind wirklich zwei gleich große Mengen mit identischen Summen gemeint? Das ist interessant. Hier könnt es tatsächlich relativ schnell mit Backtracking gehen. Muss mal nachdenken... Ist aber Freitag, da wird das nix mehr...
