Herausforderung
Schreiben Sie eine Funktion, die aus einem beliebigen Eingabearray alle Zahlenkombinationen mit einer Summe von 10 auswählt.Auf den ersten Blick ist die Aufgabe einfach. Sie müssen lediglich eine Rekursion schreiben und alle Werte sortieren.
Sie können auch ein binäres Inkrement verwenden. Um jedoch alle Werte für einen Vektor mit Zahlen der Länge N zu durchlaufen, sind 2 ^ n Iterationen erforderlich.
Zuerst wählen wir einen Sonderfall aus, nehmen wir an, dass das Array aus Zahlen> 0 besteht. Später werden wir anhand dieses Beispiels alle Fälle implementieren.SCHRITT 1
a) Betrachten Sie einen der Sonderfälle - die Summe aller Elemente des Arrays <10.
Die Logik ist einfach: Summe (V) <10, dann Summe (V) -V [i] <Summe, dh wenn die Summe der Kombinationen immer kleiner als 10 ist.
b) Wenn Summe (V) = 10 ist, dann ist die Summe Summe (V) -V [i] <Summe. Das Ergebnis ist nur eine
v .
SCHRITT 2
Wir entfernen alles Unnötige aus dem Vektor
Nehmen Sie als Beispiel das Array [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2, 2, 2, 1, 5 , 5, 5].
Es zeigt sofort, dass es keinen Sinn macht, nach Kombinationen zu suchen, wenn der Wert> 10 ist, aber alles wird sofort klar. wenn wir es sortieren:
[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20 ]]
Zu diesem Zeitpunkt können wir bereits sicher sein, dass wir alle Elemente löschen müssen, die größer als 10 sind
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]
Tatsächlich ist aber alles etwas interessanter. wir müssen den Vektor auf den Wert begrenzen, so dass V [0] + V [i] <= 10; wo ich zu N neige; Wenn jedoch V [i] = 10 ist, addieren wir 10 zum Ergebnis
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]
SCHRITT 3
In einem bereits gefilterten Array befinden sich doppelte Elemente. Wenn wir den Vektor in Untervektoren zerlegen und ihre Summe berechnen, erhalten wir so etwas
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5, 5, 5] => 20
[8, 8, 8] => 24
[9.9] => 18
Das Wesentliche meiner Gedanken ist, dass es keinen Sinn macht, Kombinationen sich wiederholender Zahlen zu berücksichtigen, wenn ihre Zahl *> 10 ist. Das heißt, wir schneiden die Vektoren ab, bis ihre Summe kleiner als 10 ist, und addieren diejenigen, die 10 sind, zum Ergebnis:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [2, 2, 2, 2]
[4] => [4]
[5, 5, 5, 5] => [5]
[8, 8, 8] => [8]
[9.9] => [9]
Als Ergebnis des dritten Schritts wird unser Vektor wie folgt sein
[1, 1, 2, 2, 2, 4, 5, 8, 9]
Wie Sie sehen können, hat sich die Größe des Vektors von 25 auf 9 verringert und ist viel kleiner (denken Sie an die Anzahl der Iterationen).
Mit negativen Zahlen
Das ist etwas komplizierter. Wir gehen davon aus, dass wir die Funktion zum Finden von Kombinationen für einen positiv sortierten Vektor basierend auf den vorherigen Einschränkungen implementiert haben.
Kamm (arr, Summe), wobei Summe der erforderliche Betrag ist, ist arr ein Vektor, der aus positiven Zahlen sortiert ist
Nehmen Sie zum Beispiel den Vektor:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12 , -10, 9]
1. Brechen Sie den VektorA = nur positive Werte
B = nur negative Werte
Und sehen Sie auch, ob wir Werte = 0 haben
2. SortierenSortieren Sie die Vektoren (positiv aufsteigend, negativ absteigend)
Überprüfen Sie den Sonderfall auf positive Zahlen (SCHRITT 1)
3. Überprüfung des PositivenAuf positive Werte prüfen
Kamm (B, 10)3. Auf Negativ prüfenErstellen Sie Kombinationen aller negativen Zahlen, jedoch mit der Einschränkung:
(Summe der Elemente modulo) <(Summe aller positiven) + 10
wir finden Kombinationen für die NEUEN Referenzsummen (die Summe der Elemente modulo + 10)
4. Gleichheit 0Wenn der Quellvektor den Wert 0 hat, addieren wir alle Kombinationen + 0 zum Ergebnis.
Infolge solcher Einschränkungen beträgt der Zeitgewinn beim Testen von Werten mit einem Array von 28 und 1000 Tests im Durchschnitt fast 42%
Achten Sie darauf, nicht nervös auszusehen. Der Autor ist nicht verantwortlich für moralisches Leiden.function combine(arr, etalon = 10) {