Ich bin über diese Frage, die ich beantworten muss (es ist technisch Hausaufgaben), ins Schwitzen gekommen. Ich habe eine Hashtabelle in Betracht gezogen, aber ich bleibe irgendwie bei den genauen Einzelheiten fest, wie ich diese Arbeit machen würde.
Hier ist die Frage:
Gegebene k Mengen von Ganzzahlen A 1 , A 2 . ., A k der Gesamtgröße O ( n ), sollten Sie feststellen, ob sie existieren a 1 A 1 , a 2 ε A 2 , .., ein k ε A k , sodass a 1 + a 2 + .. + a k -1 = a k . Ihr Algorithmus sollte in T k ( n ) laufen Zeit, wo T k ( n ) = O ( n k / 2 × log n ) für gerade k und O ( n ( k +1) / 2 ) für ungerade Werte von k .
Kann mir jemand eine allgemeine Richtung geben, damit ich näher an die Lösung herankomme?
Teilen Sie die k Mengen in zwei Gruppen. Für gerade k haben beide Gruppen jeweils k / 2 Sätze. Für ungerade k hat eine Gruppe (k + 1) / 2 und die andere hat (k-1) / 2 Sätze. Berechnen Sie alle möglichen Summen (ein Element aus jeder Menge) innerhalb jeder Gruppe. Für gerade k erhalten Sie zwei Arrays mit jeweils n k / 2 -Elementen. Für ungerade k hat ein Array n (k + 1) / 2 und das andere Array hat n (k-1) / 2 -Elemente. Das Problem wird auf den Standard reduziert. "Bei zwei Arrays überprüfen Sie, ob eine bestimmte Summe erreicht werden kann, indem Sie ein Element aus jedem Array nehmen."
Tags und Links algorithm backtracking hashtable subset-sum