Bestimmte Werte eines Arrays ausgeben.

[Lorbernd]

Hallo zusammen,
ich beschäftige mich seit kurzer Zeit mit Java und habe mir die Frage gestellt ob es möglich sei verschieden Werte aus einem Array zu holen, die eine bestimme Summe bilden.

Wenn ich z.B. ein Array habe mit folgenden Werten: 4, 6, 5, 2, 5, 7, 1, 3, 5 und möchte, dass alle Werte ausgegeben werden die zusammen 10 ergeben (ohne Mehrfachverwendung). Sodass (4 und 6), (5, 2 und 3) usw. ausgegeben werden.

Ich hoffe ich habe mein Problem verständlich beschrieben.

LG Jörg

 

[VfL_Freak]

Moin,

mal ein laxer Ansatz:
- laufe durch das Array
- prüfe die Summe des ersten Elements mit allen weiteren
- - passt Summe: ENDE
- - außer: zweiter Wert wurde schon verwendet, dann weiter duchlaufen bis es paßt oder Arrayende erreicht ist
- dann das gleiche mit zweiten Wert
- - außer: zweiter Wert wurde schon verwendet, dann dritter Wert
etc.

VG Klaus

 

[fhoffmann]

Natürlich ist das möglich. Allerdings ist dieses Problem "NP-vollständig", was bedeutet, dass das Programm exponentielle Laufzeit hat. (Das Problem ist bekannt als "Subset-Sum".)
Du solltest alle möglichn Kombinationen von Zahlen aus dem Array ausprobieren und prüfen, ob die Summe 10 ist.

 

[Tarrew]

Um die Potenzmenge deines Arrays zu berechnen, kannste am besten Guavas Sets-Klasse o. Ä. benutzen.
Der Rest ist dann trivial.

Spoiler

        Sets.powerSet(new HashSet<>(Arrays.asList(4, 6, 5, 2, 5, 7, 1, 3, 5)))
                .stream()
                .filter(l -> l.stream().mapToInt(Integer::intValue).sum() == 10)
                .collect(Collectors.toSet())
                .forEach(System.out::println);